Marbles maths challenge

#1

n and k are very large. so how can i compute (n-1)C(k-1)?
n*(n-1)…(n-k+1)/k*(k-1)…1 is not working.

#2

hey @himanshugupta8
Refer to this Marbles problem

If this resolves ur query then please mark it as resolved :slight_smile:

#3

Your code isn’t working for n=100000, k=10000

#4

Okay let me check…

#5

Hey @himanshugupta8
Yes correct, you have to use BigIntegers in C++ for that test case.

#6

You mean BigIntegers in java?right…

#7

Yup correct, though u can find user define BigInt for c++. :slight_smile:

#8

okay…thanks… i didn’t know that.
Also can you please tell me that why are you multiplying and dividing with ans in separate lines. i.e.
ans = ans*i;
ans = ans/(n-i);

Actually i was doing it in one step which isn’t passing for n=10^6 and k=10^3 and yours is passing.

#9

Hey @himanshugupta8
You can do that in one line as well
ans=(ans*i)/(n-i);
This should work according to me

#10

Yeah its passing all the test cases :slight_smile:

#11

it is working…i was writing
ans *= i/(n-i);

#12

oh
If you dont have any other doubt in this then please mark it as resolved :slight_smile:

#13

why this code is not working?
def comb(n,r):
big = max(n-r,r);
# print(big)
ans=1
i=1
while (n> big):
ans = (ans*n)/i
n-=1
i+=1
return ans

t=int(input())
while(t>0):
l=input().split(" ")
n=int(l[0])
k=int(l[1])
print(int(comb(n-1,k-1)))
t-=1

#14

Its equivale to ans=ans*(i/(n-i))
Because i may not be divisible by (n-i)
but (ans*i) will always be divisible by (n-i) here when we go into mathematics

#15

Hey @himanshugupta8
Please share it in IDE

#16

where can i find that? :sweat_smile:

#17

@himanshugupta8
Go here https://ide.codingblocks.com/
paste ur working code
press ctrl+S and click on save
Now share the url

#19

ok…

#20
#21

@himanshugupta8
Bro your code is correct but according to actual solution implemented in the backend u have to use

   ans = (ans*n)//i;