×

# EDITORIAL BYTES4 - TODO EN UNO

 2 2 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. asked 05 Feb '14, 12:06 65●1●2●8 accept rate: 50% 3★kcahdog 10.0k●28●54●129 @behalgitanshu Pls see if the indentation of the code is correct. I edited it as it was unclear earlier (06 Feb '14, 04:04) kcahdog3★ 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? (06 Feb '14, 23:22) @destination_i you are correct, it should be cnt+=freq[j] (07 Feb '14, 01:01) what if the range of values would have been large like 10^9? (12 Jul '14, 14:42) Nice explaination. (y) (15 Sep '15, 11:48)

 0 "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. answered 18 Jul '17, 13:34 17●1 accept rate: 20%
 0 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 answered 18 Jul '17, 15:35 1 accept rate: 0%
 0 Ya that i accept :) But i was saying for a general case.. you cam't say this. answered 18 Jul '17, 21:39 17●1 accept rate: 20%
 0 I am not able to understand.Please, can you explain once in the more elaborate manner? answered 18 Jul '17, 22:07 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×8
×8

question asked: 05 Feb '14, 12:06

question was seen: 5,297 times

last updated: 03 Apr '18, 00:26