 # 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.
Condition:
1<=i,j,k,x,y,z<=n

1<=test_cases<=10
1<=n<=1000

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.

2 Likes

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`.
Pseudocode:

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

PS : dont forget the mod 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.

3 Likes

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.

https://ideone.com/Id3GlG, 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