Can someone suggest better approach for the above question
2 Likes
it can be done in O(n*factors(x))
Have three frequency tables(Maps/arrays/or other DS) for counting the frequency of a particular divisor of X.
Table 1 will store number of ways to get value y(divisor of x) using just 1 number from the array.
Table 2 will store number of ways to get value y using 2 numbers from the array.
Table 3 will store number of ways to get value y using 3 numbers from the array.
Initially all values in the table is 0.
Now process the array from left to right(1…n)
for an element a in the current position and for all possible divisors(d) of X we are going to update all the tables.
if a doesn’t divide d then the tables remain same else let p=d/a.
Then table3[d]+=table2[p] i.e to get d using 3 divisors with one of them as a then we need to know the number of ways to form p using two divisor till the elements that we have seen previously.
Similarly table2[d]+=table1[p] and table1[a]+=1.
Make sure for each element first update the table 3,then table 2 then table 1 as 3 depends on 2 which again depends on 1.
Now after processing all the elements of the array the answer is table3[X].
3 Likes
The above approach mentioned by Murugappan is good.
There can be one more solution which may be easier and more intuitive. The time complexity of the approach will be still O(factors(x)*factors(x)) (worst case O(n^2) when all the array elements are factors of x) and space complexity will be O(n).
You just need 2 sets for this approach.
The idea is that, first you iterate through the input array and insert all elements which divides x into the set. The you need to again iterate through the array and for each iteration, you iterate through the set and check if the product of the two current elements divide x(the product != 0 and the elements are not equal), then you again check if the set contains the element x/(first_element * second_element) and if the element is not equal to either the first or the second element, then you increment the count. You just need to save the triplets in another set or some other data structure to check if it was counted previously.
This idea is very intuitive i guess. Below is the pseudocode:-
array(int) a
int num, count = 0
set(int) s1, s2
for i = 0 to n:
input(num)
if(num != 0 and x%num == 0):
a.insert(num)
s1.insert(num)
for i = 0 to a.length:
for j = i+1 to a.length:
if(x%(a[i]*a[j]) == 0):
num = x/(a[i]*a[j])
if(s1.exists(num) and num != a[i] and num != a[j]):
if(not(s2.exists(a[i],a[j],num)):
s2.insert(a[i], a[j], num)
count = count + 1
print(count)
You just need to check if all permutations of a[i], a[j] and num are not present in s2.
If you have any question, please ask. Hope this helps. 
1 Like
Hi, I actually made a mistake in the previous answer, the worst case time complexity will not be O(n^2).
To understand why, we need to notice a few things. According to the link provided by Divik, there are a few things to notice carefully:-
- The array contains only unique elements.
- Given, x <= 10000000(1e7).
- Given, n <= 100000(1e5).
So, what can these observations say? Lets observe carefully.
x <= 10000000(10^7) : This is the most important constraint to notice. Given a number n, the number of factors of the number will be O(sqrt(n)).
E.g. - Let us consider a number 96. What is the sqrt of 96, its ~10. So lets see what are the factors of the number 96,
1 * 96 = 96
2 * 48 = 96
3 * 32 = 96
4 * 24 = 96
6 * 16 = 96
8 * 12 = 96
There are 12 factors. So you see that for every number less than sqrt(96) ~ 10, that divides 96, there is another number greater than sqrt(96), that also divides 96.
So, it is now clear that the number of factors of the number will be O(2 * sqrt(n)), i.e. O(sqrt(n)). Given x <= 1e7. Now sqrt(x) is ~3e3, i.e. O(10^3). So, the number of factors of the largest number that can be the input will be <= (2 * 3000).
The size of the given array containing only distinct elements is 100000(1e5) and the maximum no of elements that can be a factor of the input number X, will be <= 2 * 3e3. So, you just need to check the factors of x. So, only keeping the factors of X in the array will be useful.
So, you can easily bring down the algorithm to O(sqrt(x)^2), and given x <= 1e7, this approach will easily pass the 1 sec limit. O(sqrt(x) ^ 2) = O((10^3 ) ^ 2) = O(10^6).
Hope this clears your doubt. Please ask if something is not clear. 
2 Likes
The below algorithm is followed to solve the above problem.
- Use a hash-map to count the frequency of every element in the given array.
<li>Declare a set which can store triplets, so that only unordered triplets are taken to count. </li>
<li>Iterate from 1 to sqrt(m) in a loop(let variable be i), since the maximum number by which M is divisible is sqrt(M) leaving out M. </li>
<li>Check if M is divisible by i or not and i is present in the array of integers or not, if it is, then again loop from 1 to M/i.(let the loop variable be j). </li>
<li>Again Check if M is divisible by j or not and j is present in the array of integers or not, if it is then check if the remaining number that is <strong>( (M / i) / j)</strong> is present or not. </li>
<li>If it is present, then a triplet has been formed. To avoid duplicate triplets, insert them in the set in a sorted order. </li>
<li>Check if the set the size increases after the insertion of triplet, if it does then use combinatorics to find the number of triplets. </li>
<li>To find the number of triplets, the following conditions will be there.
- If all of the Ai, Aj and Ak are unique, then number of combinations will be the prthe oduct of their frequencies.
<li>If all of them are same, then we can only choose three of them, hence the formula stands at frequenceC3. </li>
<li>If any of the two are same(let Ai and Aj), the count will be frequency[Ai]C2 * frequency[A<sub>k</sub>]</li>
// hash-map to store the frequency of every number
unordered_map<int, int> frequency;
// set to store the unique triplets
set<pair<int, pair<int, int> > > st;
// count the number of times
// every elememt appears in a map
for (int i = 0; i < n; i++) {
frequency[a[i]] += 1;
}
// stores the answer
int ans = 0;
// iterate till sqrt(m) since tnum2t is the
// mamimum number tnum2t can divide M except itself
for (int i = 1; i * i <= m; i++) {
// if divisible and present
if (m % i == 0 and frequency[i]) {
// remaining number after divison
int num1 = m / i;
// iterate for the second number of the triplet
for (int j = 1; j * j <= num1; j++) {
// if divisible and present
if (num1 % j == 0 and frequency[j]) {
// remaining number after divison
int num2 = num1 / j;
// if the third number is present in array
if (frequency[num2]) {
// a temp array to store the triplet
int temp[] = { num2, i, j };
// sort the triplets
sort(temp, temp + 3);
// get the size of set
int setsize = st.size();
// insert the triplet in ascending order
st.insert({ temp[0], { temp[1], temp[2] } });
// if the set size does not increase after
// insertion, it means a new triplet is found
if (setsize != st.size()) {
// if all the number in triplets are unique
if (i != j and j != num2)
ans += frequency[i] *
frequency[j] *
frequency[num2];
// if Ai and Aj are same among triplets
else if (i == j && j != num2)
ans += (frequency[i] *
(frequency[i] - 1) / 2)
* frequency[num2];
// if Aj and Ak are same among triplets
else if (j == num2 && j != i)
ans += (frequency[j] *
(frequency[j] - 1) / 2)
* frequency[i];
// if three of them are
// same among triplets
else if (i == j and j == num2)
ans += (frequency[i] *
(frequency[i] - 1) *
(frequency[i] - 2) / 6);
// if Ai and Ak are same among triplets
else
ans += (frequency[i] *
(frequency[i] - 1) / 2)
* frequency[j];
}
}
}
}
}
}
Please let me know in case of any problem.
1 Like
baiscally the idea is find all factors a*b=x
then let a=x * y
b=p * q
then we want to count number of tuples with values (x,y,b),(a,p,q)
If all factors are present in array it can give TLE as the complexity
is O(n^2)
You are most welcome.
Number of factors for a given number (n) can’t be equal to n. I don’t know the proper upper bound but usually its O(n^(1/3)).
If Ai and Aj are same and Ak is different with frequencies f1, f2 and f3 respectively, then ans will be (f1*(f2-1)/2)*f3 OR ((f1-1)*f2/2)f3? Because it makes diference. Let’s say f1=5, f2=3 and f3=4, then (f1(f2-1)/2)*f3 equals 20 but ((f1-1)*f2/2)*f3 equals 24. Please tell me how are you calculating the combinations.
Hey, could you please explain how the complexity is O(NlogN)?
1 Like