# Project Euler #53: Combinatoric selections

# Project Euler #53: Combinatoric selections

+ 2 comments Hint : Solve this Hacker Rank : nCr table challenge first. Pascal triangle is the shortest way in my opinion

+ 0 comments for solving this problem you have 2 approaches 1 create an array with all the factorials and then just get the value from the array instead of re calculate it over and over again 2 use pascal triangle....

best of luck

+ 0 comments For a faster approach, notice that maximum input limit of k is 10^18. For n=1000, all r>7 exceeds kmax. From this we can conclude that we just need to find that r for which nCr exceeds k.

+ 3 comments My code is passing all the test cases except no.3. Its showing wrong answer. Please tell me what is wrong in this code.

unsigned long long C[1001][1001], i, j, k, N, K, coun = 0, flag = 0;

int main()

{

cin >> N >> K;

for (i = 1; i <= 1000 && i <= N; i ++)

{

for (j = 0; j <= i; j ++)

{

if (j == 0 || j == i)

C[i][j] = 1;

else

{

if (j == 1 || j == i-1)

C[i][j] = i;

else

C[i][j] = C[i-1][j] + C[i-1][j-1];

}

}

}

for (i = 1; i <= N; i ++)

{

flag = 0;

for (j = 0; j <= i; j ++)

{

if (C[i][j] > K)

{

flag = 1;

break;

}

}

if (flag == 1)

coun += (i - 2*j + 1);

}

cout << coun;

return 0;

}

Thanks !!

+ 0 comments Hint: one does not have to compute all nCr but rather consider how nCr changes as n and r changes.

Sort 15 Discussions, By:

Please Login in order to post a comment