You are not logged in. Please login at www.codechef.com to post your questions!

×

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

behalgitanshu's gravatar image

3★behalgitanshu
65128
accept rate: 50%

edited 06 Feb '14, 04:03

kcahdog's gravatar image

3★kcahdog
10.0k2854129

@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_i2★

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

(07 Feb '14, 01:01) rishul_nsit4★

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

(12 Jul '14, 14:42) abhigoyal19943★

Nice explaination. (y)

(15 Sep '15, 11:48) utkarsh134★

"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.

link

answered 18 Jul '17, 13:34

sahil070197's gravatar image

5★sahil070197
171
accept rate: 20%

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

link

answered 18 Jul '17, 15:35

trailblazer995's gravatar image

5★trailblazer995
1
accept rate: 0%

Ya that i accept :) But i was saying for a general case.. you cam't say this.

link

answered 18 Jul '17, 21:39

sahil070197's gravatar image

5★sahil070197
171
accept rate: 20%

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

link

answered 18 Jul '17, 22:07

sameer_hack's gravatar image

3★sameer_hack
1
accept rate: 0%

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

link

answered 25 Aug '18, 17:32

ace4's gravatar image

4★ace4
11
accept rate: 0%

edited 25 Aug '18, 17:32

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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