CODEWITHSUNDEEP
algorithmmathgreatest-common-divisor
Hoang Van Thien
Hoang Van Thien

Reputation: 51

Check if an integer is GCD of some elements in a given set

Given a set of positive integers and an integer k. All of the elements in the set is divisible by k.

How to check if k is greatest common divisor of some elements in the set?

My idea: For every element a[i] in the set, I divide it by k. Then I get GCD of all of the element in the set (which was changed after I divided). If the GCD is equal to 1, then k is GCD of some elements in the set.

I have make some test cases and I see it right. But the online judge doesn't accept. Please give me an idea, or check my algorithm and fix it. Thank you very much.

Let me speak it more clearly:

For instance, a = {10, 15, 18}:

k = 5 is GCD(10, 15). Answer is true

k = 3 is GCD(15, 18). Answer is true

k = 1 is GCD(10, 15, 18). Answer is true

k = 6 is not GCD of any group which contains more than 2 integers. Answer is false

Size of the set: <= 100000

EDIT: Sorry for giving a wrong example. It was my mistake. k = 3 is not GCD(10, 18). But I thought you might know this is 15 instead, right. :) Thanks for your answers, comments and contribution. I have voted an accepted answer below.

Upvotes: 0

Views: 1086

Answers (2)

guillaume girod-vitouchkina
guillaume girod-vitouchkina

Reputation: 3079

1 the question is incoherent with the example:

for 10, 15, 18:

  • 3 is not a divisor of 10, neither 6
  • there is no common divisor

2 your question can be reduced like that :

  • k divides every elements, so divide them => new "reduced" set
  • if k was GCD of some subset, then, the corresponding reduced subset has 1 as GCD (they are prime together)
  • so we can forget k

3 the problem is now: given a set, is it a subset of elements prime together (or with 1 as GCD) ?

but if it is true from a subset, it is true for all elements.

So your algorithm is good: take A1, A2, and GCD, then GCD of this an A3, ...

If at some point you get 1, it is finished.

Upvotes: 2

Paulo
Paulo

Reputation: 1498

int gcd(int a, int b) {
  int c;
  while(a != 0) {
     c = a;
     a = b%a;
     b = c;
  }
  return b;
}

bool function(int[] a, int n, int k) {
    int numberOfGCD = 0;
    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++)
            if(gcd(a[i], a[j]) == k) numberOfGCD++;
    return numberOfGCD > 1;
}

Upvotes: 0

Related Questions