How to solve this mathematical question?

This question was asked in Kaleyra Recruitment Challenge on HackerEarth which is now completed. The question was as follows:

How many distinct ways are there such that (i+2j+k)%(x+y+2z) = 0.


For n =1, ans was 1
For n=2, ans was 15
For n=3, ans was 117

Bruteforce was an obvious no as complexity was going to n^6.
The answer probably lies in using permutation taking into consideration some cases but I wasn’t able to find all cases as my answer was not correct for n=3 and beyond.


This was from Kaleyra challenge from Hackerearth which was completed.

As you can see the numerator and denominator are basically the same expression i.e. i+2*j+k
The possible values of this range from 4 to 4*n. Let’s denote arr[x] be the number os ways of getting the i+2*j+k = x. Now for each possible x such that sum arr[x]*arr[y] such y%x==0.

 ans = 0
 for all x such that arr[x]>0:
         y = 1
         while x*y <= 4*n
               ans += arr[x]*arr[x*y]

PS : dont forget the mod :smile:

Also finding no of ways of getting i+2*j+k = x is just an extension of getting x+y+z=n you can google that. or just comment below I’ll explain it.


Hi! can you explain how to find solutions for i + 2j + k = x.

Yup, the first line already stated that.

1 Like

Thanks for the reply, let me analyze this.

i+2*j+k = x is the same as finding the coefficient of y^x in the sequence(y + y^2 + .., + y^n)*(y^2 + y^4 + ... + y^2n)*(y + y^2 + .., + y^n). The mathematical concept you’ll need to solve this efficiently is negative binomial theorem., you should notice that it is type of dp consider possible values using i,j and then possible value and k in n^2, and then find modulo intersection using sieve. without sieve i got tle in main problem, hence i guess sieve is necessary, or u could use gcc optimizer.

1 Like