hi guys,
I need help with this question. I want to know how should I approach this question. The question was a part of ValueLabs full stack hiring challenge and the contest is already over.
1 Like
Solution:-
Let a= A[i];
So, (a+b+c) should be divisible by a, this is only possible if (b+c) is divisible by a , so all you gotta do is find the number of pairs in the array whose sum is divisible by ‘k’ using this :- Count pairs in array whose sum is divisible by K - GeeksforGeeks
Do the pre-processing and calculate it for all k's from 1 to 100.
It might be possible that we may again include the same triplet, using this approach. Correct me if I’m wrong.
You have to divide the final answer by 3, did not include that as it was unserstandable I gues.s…
I have read this post on stack overflow and understood the approach but i am little bit confused in the part where we are using frequency of elements.
for(int i=0;i<v.size();i++){
if(m1[v[i][0]]>0 && m1[v[i][1]]>0 && m1[v[i][2]]>0)
{
if(v[i][0]==v[i][1])
ans+=((m1[v[i][0]]*(m1[v[i][1]]-1)*m1[v[i][2]]));
else if(v[i][1]==v[i][2])
ans+=((m1[v[i][0]]*(m1[v[i][1]]-1)*m1[v[i][2]]));
else if(v[i][0]==v[i][2])
ans+=((m1[v[i][1]]*(m1[v[i][0]]-1)*m1[v[i][2]]));
else
ans+=(m1[v[i][0]]*m1[v[i][1]]*m1[v[i][2]]);
}
}
If anyone gets this please clear it for me too …
I think our approach might fail as in question it is clearly mentioned that the number should be divisible by exactly one of numbers (a/b/c).
Nothing like that. You didn’t understood my solution as I didn’t explain clearly. 
Busy, will write detailed answer soon.
Here is My solution. It is in python. Basically else part is redundant in it.
tag: Basic Combinatorics required + Frequency array.
required equations
1: nC1 * nC1 *nC1
2 : nC2 *nC1
you can write nC2 = (n*(n-1)/2)
As here clearly mentioned that,
1 <= A[i] <= 100, triplet sum like (a,b,c) must be in range 3 <= sum(a,b,c) <= 300.
I am pretty sure that the direct approach would pass the time constraint.
algorithm : -
1. for every sum in range(3,300)
a. we find a unique triplet that can be formed using the number of the given array.
b. And for every such unique triplet, we have 6 permutations cause here, we are considering with respect to indexes.
Like if we have sum = 5 and A[0] = 2,A[1] = 2, A[2] = 1.
ans for this would be 6 because (0,1,2),(0,2,1),(1,0,2),…
How can you know whether a triplet is unique or not:-
This can be done using a 3d array-like,
bool memo[101][101][101] ;
memo[i][j][k] should keep the number in a sorted order,
i<=j<=k
Another that need to keep in mind is sum should be divisible by exactly one of the triplet number:-
sum = 11, a valid triplet is (5,5,1)
but for sum = 8, this triplet is not valid (4,2,2).
To determine the number of time a triplet will occur:-
This can be done using a frequency array.
sum = 5, a valid triplet is (2,2,1) = (a,b,c)
fre (i) = frequency of number i.
N = fre(a)
as hare a == b, ans = 6* (Nc2)*frequency©
if a != b and a!=c and b!=c
ans = fre(a)*fre(b)*fre©*6
How to find a triplet for a sum:
for sum in (3,300):
for a in range(1,100):
for b in range(1,100):
c = sum-a-b;
I think this might help you.
My solution in python. my approach is to store all possible triplets from range [1,100] and find our answer by counting how many times each triplet is present in our array
2 Likes
You should get the triplest index paires_how many paires?_ for the sum answer for it values that accept complete division on one only of the values, that what I understand as far so.
@macdod Can you please explain how you are using frequency of elements to get answer, that part is not clear to me …??
@rk_221b Consider the pair (1,2,2) and the frequencies of the elements are 1->4, 2-> 3, so the possible number of pairs that can be formed from these numbers are 4*((3*2)/2), just simple combinations and later it can be permuted in 3! ways. Here it is being divided by 2 because of duplicate 2s.
Got it thanks
Can anyone provide an Online Judge link of this problem?