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.
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
google it
[Deleted] Wrong approach!
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
Ohh, you are correct, then can we extend this idea somehow to solve this problem?
I don't think so, the problem is NP, below I mentioned an idea that works
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.
test case
$$$2$$$
$$$4$$$ $$$10$$$
The smallest number does not divide anything still the answer is 1.
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.
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.
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
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.
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.
I think just adding one more condition might make it correct.
check gcd with whole set and replace it with number producing highest gcd.
No, it will not. Consider the case [6,14,7,3].
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)
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)
why are you checking only till sqrt(maxvalue), how will it work for the case 21, 14
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
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.
Problem is NP. What's the constrain on A[i] ?
This problem is called the hitting set problem and it is known to be NP-complete. It is equivalent to the set cover problem.
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.