CSES Solutions – Common Divisors
You are given an array of N positive integers. Your task is to find two integers such that their greatest common divisor is as large as possible.
Example:
Input: N = 5, arr[] = {3, 14, 15, 7, 9}
Output: 7
Explanation: GCD(14, 7)=7 which is the maximum possible among all the pairsInput: arr[] = {1, 12, 15, 3, 8}
Output: 4
Explanation: GCD(12, 8)=4 which is the maximum possible among all the pairs
Approach: To solve the problem, follow the below idea:
First count the occurrences of each integer in the array. This is done using a count array, where the index represents the integer and the value at that index represents the number of occurrences of that integer.
Then, to find the largest GCD, iterate from the largest possible integer down to 1 and checking if there are at least two multiples of the current integer in the array (since the GCD of two numbers can be at most the smaller number). If there are, that means the current integer is the largest GCD, so it is returned as the result.
Step-by-step algorithm:
- Initialize the count array count with zeros.
- Iterate through the integers in arr[] and update the count array count.
- Iterate through numbers from 1000000 down to 1.
- For each number i:
- Count the number of multiples of i in the array count.
- If there are at least two multiples of i, print i and return.
Below is the implementation of the algorithm:
#include <iostream>
using namespace std;
// Function to find the largest common divisor
long long findLargestCommonDivisor(long long count[])
{
// Iterate from 1000000 down to 1
for (int i = 1000000; i >= 1; i--) {
// Count the number of multiples of i
long long multiples = 0;
for (int j = i; j <= 1000000; j += i) {
multiples += count[j];
}
// If there are at least two multiples of i, print i
// and return
if (multiples >= 2) {
cout << i;
return 0;
}
}
return 0;
}
int main()
{
// Number of integers in the arr
long long n = 5;
// Array to store the integers
long long arr[n] = { 3, 14, 15, 7, 9 };
// Array to count the occurrences of each integer
long long count[1000001] = {};
// Read the integers and update the count arr
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
findLargestCommonDivisor(count);
}
import java.util.Arrays;
public class Main {
// Function to find the largest common divisor
public static void findLargestCommonDivisor(long[] count) {
// Iterate from 1000000 down to 1
for (int i = 1000000; i >= 1; i--) {
// Count the number of multiples of i
long multiples = 0;
for (int j = i; j <= 1000000; j += i) {
multiples += count[j];
}
// If there are at least two multiples of i, print i
// and return
if (multiples >= 2) {
System.out.println(i);
return;
}
}
}
public static void main(String[] args) {
// Number of integers in the arr
int n = 5;
// Array to store the integers
long[] arr = {3, 14, 15, 7, 9};
// Array to count the occurrences of each integer
long[] count = new long[1000001];
Arrays.fill(count, 0);
// Read the integers and update the count arr
for (int i = 0; i < n; i++) {
count[(int) arr[i]]++;
}
findLargestCommonDivisor(count);
}
}
from collections import defaultdict
# Function to find the largest common divisor
def find_largest_common_divisor(count):
# Iterate from 1000000 down to 1
for i in range(1000000, 0, -1):
# Count the number of multiples of i
multiples = 0
for j in range(i, 1000001, i):
multiples += count[j]
# If there are at least two multiples of i, print i and return
if multiples >= 2:
print(i)
return
def main():
# Number of integers in the array
n = 5
# Array to store the integers
arr = [3, 14, 15, 7, 9]
# Dictionary to count the occurrences of each integer
count = defaultdict(int)
# Read the integers and update the count dictionary
for num in arr:
count[num] += 1
find_largest_common_divisor(count)
if __name__ == "__main__":
main()
// Function to find the largest common divisor
function findLargestCommonDivisor(count) {
// Iterate from 1000000 down to 1
for (let i = 1000000; i >= 1; i--) {
// Count the number of multiples of i
let multiples = 0;
for (let j = i; j <= 1000000; j += i) {
multiples += count[j];
}
// If there are at least two multiples of i, print i and return
if (multiples >= 2) {
console.log(i);
return;
}
}
}
// Main function
function main() {
// Number of integers in the array
const n = 5;
// Array to store the integers
const arr = [3, 14, 15, 7, 9];
// Array to count the occurrences of each integer
const count = new Array(1000001).fill(0);
// Read the integers and update the count array
for (let i = 0; i < n; i++) {
count[arr[i]]++;
}
findLargestCommonDivisor(count);
}
main();
Output
7
Time Complexity: O(N * log(N)), where N is the maximum element in the array arr[].
Auxiliary Space: O(N)
Contact Us