FifthThread's blog

Google Online Assesment Question
By FifthThread, history, 3 years ago, In English

find minimum number of integers, (where each such integer>=2) that divide all array elements. For example, if the array is [2,4,6,8,10] then the answer is 1 (because 2 divides all array elements). Another example, if the array is [2,3,4,9] then the answer is 2 (because we need at least 2 different numbers, 2 and 3, that satisfy the conditions).

Constraints: N<=10^3

Can someone help, I am not able to solve this problem.

  • Vote: I like it
  • -15
  • Vote: I do not like it

Comments Comments (23)
| Write comment?
»
3 years ago, # |
  Vote: I like it -14 Vote: I do not like it

I think we can use two loops like sieve of erasthones and every time a new prime no. Factor is found for first time, we increase the count

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

google it

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[Deleted] Wrong approach!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    That is wrong, when you do a min cost max flow the cost of an edge is (amount of flow) * cost therefore that will always return N for both maximum flow and minimum cost

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh, you are correct, then can we extend this idea somehow to solve this problem?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I don't think so, the problem is NP, below I mentioned an idea that works

        → Reply
»
3 years ago, # |
  Vote: I like it -19 Vote: I do not like it

I think this might work. Sort the numbers. We can see that smallest number is not divisible by any other number except itself. So, it should definitely come in our group of numbers. Now, find all the multiples for this number and mark them visited. Now, repeat the same step for the next unvisited smallest number and so on.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    test case

    $$$2$$$

    $$$4$$$ $$$10$$$

    The smallest number does not divide anything still the answer is 1.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was wandering can greedy might work. Lets say we calculate prime factor for each number. Then maintain a frequency array which contain this prime divide how many numbers present in the array. After that we take the prime which has max frequency , this can be done using priority_queue or set. Discard all those numbers which this prime divide. While discarding we also update the frequency array (and in set as well) i.e subtract 1 for all the primes of this number, keep discarding and adding to answer till the array becomes empty.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this is just standard stupid min vertex cover of bipartite graph. Don't know why they would ask these trivial applications of such advanced algorithms in a hiring contest.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I think that the "standard stupid min vertex cover of bipartite graph" fails with the test case {2,6,15}, I don't know what is your bipartite graph, but if it is the one I imagine it should return 3 as minimum vertex cover, however the answer is clearly 2. Your concept of minimum vertex cover I think you have it wrong, you can search here https://en.m.wikipedia.org/wiki/Vertex_cover

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

EDIT: This solution is incorrect. Thanks to GusFring for pointing out.

Maintain a set of numbers, call it S (Initially it will be empty). Iterate over the array and while inserting a new element a[i], find gcd(a[i], sj), iterating over all elements sj of set S. If any gcd is greater than 1, then replace that element in the set with the gcd and break, Otherwise all gcds are 1, then insert a[i] into the set. At the end, our answer will be the size of the set.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    I believe your logic is flawed. Take for example a = [6, 7, 14, 3].

    i = 0, S = {6}

    i = 1, S = {6, 7}

    Now when i = 2, a[i] = 14, gcd(6, 14) = 2. So we replace 6 with 2. S = {2, 7}

    i = 3, S = {2, 3, 7}

    Thus producing a wrong answer.1. 1.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think just adding one more condition might make it correct.

      check gcd with whole set and replace it with number producing highest gcd.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, it will not. Consider the case [6,14,7,3].

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    ig it will give wrong answer for test 6 14 3 7

    the answer is 2 (3 and 7), but according to your approach answer is 3 (2,3,7)

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that this problem is NP, if there is a quick solution it is taking advantage of the fact that the maximum value of the elements is small, you can make a bit mask and taking advantage of some factoring properties and we could get some complexity similar to O (2 ^ (primes up to sqrt (maxvalue)) * N)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    why are you checking only till sqrt(maxvalue), how will it work for the case 21, 14

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      well, the main idea is to make a bitmask to all the primes less than or equal to sqrt (maxvalue), you iterate through all the masks, you look for the numbers that are divisible by at least one prime of that mask and if not then there can only be a prime greater than the square root in the factorization of a number, in case that number is not divisible by any prime of the mask, then we should mark it and add it to the answer, we can keep the primes greater than the root quickly, you can use a set or normal an array of boleans, and the final answer is mask size + different primes greater than the root you had to use

      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Will this work in case that the numbers in the array are of the type, (odd greater than 50) * (some other factor) for eg. take this case:

    5

    142 213 284 355 426

    The answer should be 1(71).

    Consider similar cases with more primes that are greater than 50 or so.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem is NP. What's the constrain on A[i] ?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This problem is called the hitting set problem and it is known to be NP-complete. It is equivalent to the set cover problem.

→ Reply
»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

If A[i] is not very large we could find the smallest prime factor of every number in the array . And the number of distinct such primes will be our answer.

→ Reply