EDITORIAL BYTES4 - TODO EN UNO

general
,
1

Problem Link: http://www.codechef.com/problems/BYTES4

Difficulty : Medium Hard

Strategy : GCD,Sieve

Explanation :
Here we have to find the maximum GCD of all the pairs possible.
The most trivial method is to evaluate the GCD of each possible pair and store the maximum but this would take O(n^2) time complexity but it would lead to TLE.
We can make a algorithm with better complexity using the fact that the values of the integers has an upperbound . We will use a sieve like approach to solve this problem .
Now first lets solve another problem , given a value X we have to tell whether a pair has a GCD equal to X . This can be done by checking that how many elements in the array are multiple of X. If the number of such multiples is greater than 1 , then X will be a GCD of some pair. Now to solve this problem , we can check all the values of X from 1000000 to 1 whether they can be a GCD of some pair.

Pseudocode for the problem :

//Here MAX is the maximum element in the array
//freq[i] stores the frequency of i in the array
for i = MAX to 1 :
    cnt = 0
    j = i 
    while j <= MAX :
    if freq[j]>0 :
        cnt++ 
    j += i   
if cnt > 1 :
     ans = i	
     break

Now , the complexity of this algorithm is given by the divisor summatory function and this case it will be D(MAX) and the time complexity of this function is till an open problem known as the Dirichlet divisor problem. But for the given time limit this solution will pass.

2 Likes
2

@behalgitanshu Pls see if the indentation of the code is correct. I edited it as it was unclear earlier

3

Should it not be cnt += freq[j]? What happens if the input it T=5, and arr[] = {1, 1, 1, 10, 10}.
Here pairwise maximum GCD is 10, but since when i = 10, the cnt will be 1, and hence will proceed to the point where i = 1 and give output at 1. Is there anything I’m missing here?

4

@destination_i you are correct, it should be cnt+=freq[j]

5

what if the range of values would have been large like 10^9?

6

Nice explaination. (y)

7

“given a value X we have to tell whether a pair has a GCD equal to X . This can be done by checking that how many elements in the array are multiple of X. If the number of such multiples is greater than 1 , then X will be a GCD of some pair”
This is incorrect consider say, array is [6,18], X=3, gcd of only pair is 6 and not 3.

8

No it’s not incorrect, this is because here we are iterating from MAX(largest element of array) to 1, so in your example X = 6 will come before X = 3, hence the solution is correct

9

Ya that i accept :slight_smile: But i was saying for a general case… you cam’t say this.

10

I am not able to understand.Please, can you explain once in the more elaborate manner?

11

Please Help, I am unable to understand why my code gives Wrong Answer!
Code-here