PROBLEM LINKS:Setter : Vatsal GuptaTester : Shubham GroverDIFFICULTY:EasyMedium PREREQUISITES:Number Theory EXPLANATION:Firstly, create a count array which stores the count of each number in the array (since the maximum number in the array is no more than 10^6). Since we know that for a number x the elements which satisfies the condition (A%x==0) are actually the multiples of x and hence we need to travel the multiples for every number, so clearly the idea is Sieve of Eratosthenes. Important thing to note here is, since a number can appear any number of times, we cannot travel from a number to all it’s multiples more than once (that will result in TLE verdict). For that we maintained the count array and now for every number we travel to it’s multiples once and subtract the value of the count of that number from all it’s multiples (i.e. count[multiple]= max(count[multiple] count[x], 0) ). Complexity: O(n*logn), where n<=10^6 SETTER'S SOLUTION:Can be found here asked 11 Oct '16, 12:36
