Hello everyone . I am new to cp and recently i came upon the marble problem(MARBLES Problem - CodeChef). I know answer is n-1Ck-1 .
This is my solution and is getting wrong answer . Can you guys tell me where i am wrong?
SOLUTION—
#include<bits/stdc++.h>
using namespace std;
unsigned long long ncr(int n,int r){
unsigned long long res=1LL;
for(int i=1;i<=r;i++){
res=res*(n)/i;
n–;
}
return res;
}
int main(){
int test,n,r;
cin>>test;
for(int i=0;i<test;i++){
cin>>n>>r;
if(n==r) cout<<“1”<<endl;
else if(n<r) cout<<“0”<<endl;
else cout<<ncr(n-1,r-1)<<endl;;
}
}
your code can’t be copied ?!
btw change that n- to n–
It is - - it’s just showing as single -
hey the problem is in front of you. you are applying a loop of l and multiplying n times by decreasing n in every loop but that does not ensure that you are finding 123…(n-1) what if n is 10 and l is 2 you are finding (109)/(12) but you need to find (123…10)/(1*2).
Hope you get it.
It’s 10!/(8!*2!) Which is (9 10)/(12 )
There is an overflow problem. You are always iterating from 1…r . Try to calculate 102 C 86. Your algo will end up calculating huge intermediate numbers and will overflow. What you can do is loop to min(r, n-r).
2 Likes
oh yes, sorry didn’t see it. i think you can do min(r, n-r) for more optimisation.
also typecast your numerator to (unsigned long long).
1 Like
Yeah … I got it … Thanks
Yeah , that’s the thing . I got that . Thanks man , really appreciate your help .