Binomial coefficient in Java

up vote
1
down vote

favorite

Find nCr for given n and r.

Input:

First line contains no of test cases T, for every test case 2
integers as inputs (n,r).

Output:

Compute and print the value in separate line. Modulus your
output to 10^9+7. If n

Constraints:

1<=T<=50

1<=n<=1000

1<=r<=800

Example:

Input:

1

3 2

Output:

3

My approach:

import java.util.Scanner;
import java.lang.Math;
import java.math.BigInteger;

class GFG 

 private static int calcBinCoeff (int num, int r) 

 BigInteger numerator = new BigInteger("1");
 int limit = (int)(Math.pow(10,9) + 7);
 BigInteger modulus = new BigInteger(String.valueOf(limit));

 for (int i = num; i > num - r ; i--) 
 BigInteger ind = new BigInteger(String.valueOf(i));
 numerator = numerator.multiply(ind);
 

 BigInteger fact = new BigInteger("1");

 for (int i = 2; i <= r; i++) 
 BigInteger elem = new BigInteger(String.valueOf(i));
 fact = fact.multiply(elem);
 

 BigInteger ans = (numerator.divide(fact)).mod(modulus);

 return ans.intValue();
 

 public static void main (String args) 
 try (Scanner sc = new Scanner(System.in)) 
 int numTests = sc.nextInt();

 while (numTests-- > 0) 
 int num = sc.nextInt();
 int r = sc.nextInt();

 System.out.println(calcBinCoeff(num, r));

I have the following questions with regards to the above code:

1.Is there a smarter way to approach this question?

How can I improve the space and time complexity of the given question?

Have I gone too overboard by using BigInteger Library for this question?

Reference

asked 3 hours ago

Anirudh Thatipelli

256211

add a commentÂ |Â

up vote
1
down vote

favorite

Find nCr for given n and r.

Input:

First line contains no of test cases T, for every test case 2
integers as inputs (n,r).

Output:

Compute and print the value in separate line. Modulus your
output to 10^9+7. If n

Constraints:

1<=T<=50

1<=n<=1000

1<=r<=800

Example:

Input:

1

3 2

Output:

3

My approach:

import java.util.Scanner;
import java.lang.Math;
import java.math.BigInteger;

class GFG 

 private static int calcBinCoeff (int num, int r) 

 BigInteger numerator = new BigInteger("1");
 int limit = (int)(Math.pow(10,9) + 7);
 BigInteger modulus = new BigInteger(String.valueOf(limit));

 for (int i = num; i > num - r ; i--) 
 BigInteger ind = new BigInteger(String.valueOf(i));
 numerator = numerator.multiply(ind);
 

 BigInteger fact = new BigInteger("1");

 for (int i = 2; i <= r; i++) 
 BigInteger elem = new BigInteger(String.valueOf(i));
 fact = fact.multiply(elem);
 

 BigInteger ans = (numerator.divide(fact)).mod(modulus);

 return ans.intValue();
 

 public static void main (String args) 
 try (Scanner sc = new Scanner(System.in)) 
 int numTests = sc.nextInt();

 while (numTests-- > 0) 
 int num = sc.nextInt();
 int r = sc.nextInt();

 System.out.println(calcBinCoeff(num, r));

I have the following questions with regards to the above code:

1.Is there a smarter way to approach this question?

How can I improve the space and time complexity of the given question?

Have I gone too overboard by using BigInteger Library for this question?

Reference

asked 3 hours ago

Anirudh Thatipelli

256211

add a commentÂ |Â

up vote
1
down vote

favorite

Find nCr for given n and r.

Input:

First line contains no of test cases T, for every test case 2
integers as inputs (n,r).

Output:

Compute and print the value in separate line. Modulus your
output to 10^9+7. If n

Constraints:

1<=T<=50

1<=n<=1000

1<=r<=800

Example:

Input:

1

3 2

Output:

3

My approach:

import java.util.Scanner;
import java.lang.Math;
import java.math.BigInteger;

class GFG 

 private static int calcBinCoeff (int num, int r) 

 BigInteger numerator = new BigInteger("1");
 int limit = (int)(Math.pow(10,9) + 7);
 BigInteger modulus = new BigInteger(String.valueOf(limit));

 for (int i = num; i > num - r ; i--) 
 BigInteger ind = new BigInteger(String.valueOf(i));
 numerator = numerator.multiply(ind);
 

 BigInteger fact = new BigInteger("1");

 for (int i = 2; i <= r; i++) 
 BigInteger elem = new BigInteger(String.valueOf(i));
 fact = fact.multiply(elem);
 

 BigInteger ans = (numerator.divide(fact)).mod(modulus);

 return ans.intValue();
 

 public static void main (String args) 
 try (Scanner sc = new Scanner(System.in)) 
 int numTests = sc.nextInt();

 while (numTests-- > 0) 
 int num = sc.nextInt();
 int r = sc.nextInt();

 System.out.println(calcBinCoeff(num, r));

I have the following questions with regards to the above code:

1.Is there a smarter way to approach this question?

How can I improve the space and time complexity of the given question?

Have I gone too overboard by using BigInteger Library for this question?

Reference

asked 3 hours ago

Anirudh Thatipelli

256211

Find nCr for given n and r.

Input:

First line contains no of test cases T, for every test case 2
integers as inputs (n,r).

Output:

Compute and print the value in separate line. Modulus your
output to 10^9+7. If n

Constraints:

1<=T<=50

1<=n<=1000

1<=r<=800

Example:

Input:

1

3 2

Output:

3

My approach:

import java.util.Scanner;
import java.lang.Math;
import java.math.BigInteger;

class GFG 

 private static int calcBinCoeff (int num, int r) 

 BigInteger numerator = new BigInteger("1");
 int limit = (int)(Math.pow(10,9) + 7);
 BigInteger modulus = new BigInteger(String.valueOf(limit));

 for (int i = num; i > num - r ; i--) 
 BigInteger ind = new BigInteger(String.valueOf(i));
 numerator = numerator.multiply(ind);
 

 BigInteger fact = new BigInteger("1");

 for (int i = 2; i <= r; i++) 
 BigInteger elem = new BigInteger(String.valueOf(i));
 fact = fact.multiply(elem);
 

 BigInteger ans = (numerator.divide(fact)).mod(modulus);

 return ans.intValue();
 

 public static void main (String args) 
 try (Scanner sc = new Scanner(System.in)) 
 int numTests = sc.nextInt();

 while (numTests-- > 0) 
 int num = sc.nextInt();
 int r = sc.nextInt();

 System.out.println(calcBinCoeff(num, r));

I have the following questions with regards to the above code:

1.Is there a smarter way to approach this question?

How can I improve the space and time complexity of the given question?

Have I gone too overboard by using BigInteger Library for this question?

Reference

java beginner interview-questions

asked 3 hours ago

Anirudh Thatipelli

256211

asked 3 hours ago

Anirudh Thatipelli

256211

asked 3 hours ago

Anirudh Thatipelli

256211

asked 3 hours ago

Anirudh Thatipelli

256211

asked 3 hours ago

Anirudh Thatipelli

256211

add a commentÂ |Â

3 Answers
3

active

oldest

votes

up vote
1
down vote

Given the product formula

$$binom nk = prod_i=1^k fracn-k+ii tag1$$

and the symmetry property

$$binom nk = binom nn-k tag2$$

of the binomial coefficient, you can implement the calculation in the following way which avoids fractional intermediate values as well as looping more than $lfloor fracn2rfloor$ times.

public static BigInteger calcBinCoeff(BigInteger n, BigInteger k)

 BigInteger bin; // binomial coefficient
 BigInteger nom; // nominator
 BigInteger den; // denominator

 if (k.shiftLeft(1).compareTo(n) == 1)
 return calcBinCoeff(n, n.subtract(k)); // (2)

 bin = BigInteger.ONE;
 nom = n;
 den = BigInteger.ONE;

 while (den.compareTo(k) < 1) // (1)
 
 bin = bin.multiply(nom).divide(den);
 nom = nom.subtract(BigInteger.ONE);
 den = den.add(BigInteger.ONE);
 

 return bin;

Using long would overflow for $1000 choose 500$.

answered 1 hour ago

aventurin

25017

I've overread the 10^9+7 modulus. With than limitation you could actually use long as @MartinR pointed out in another comment.
â€“Â aventurin
50 mins ago

add a commentÂ |Â

up vote
1
down vote

Is there a smarter way to approach this question?

We'll see in a moment. Parts of it can be improved for sure.

How can I improve the space and time complexity of the given question?

You can't. The complexity will remain the same. The changes you can make might give small increases in performance or decrease memory usage, but the complexity will remain the same.

Have I gone too overboard by using BigInteger Library for this question?

I thought at first that it was possible to use just long, but I'm afraid not. Because of 1000 nCr 500, and such big numbers, you are stuck with BigInteger.

You can use BigInteger.valueOf instead of using the constructor with a String.

You can save some time by using the symmetric property of nCr if r > n / 2. For example, 100 nCr 80 is the same as 100 nCr 20.

You can use just one for-loop instead of two:

value = 1;
for (int i = 0; i < r; i++) 
 value = value * (n - i) / (i + 1);

return value;

I used something similar in a project of mine (where I used double instead and thus didn't have to think about truncating integers - an issue which is fixed above thanks to Martin R).

edited 1 hour ago

answered 2 hours ago

Simon Forsbergâ™¦

48.2k7126285

Yes, 1000 choose 500 will overflow with long.
â€“Â aventurin
1 hour ago

1

It should be value = value * (n - i) / (i + 1); so that the intermediate results are integers. But reducing value = value % M in each step could still produce a wrong result, try it with $ binom 103 bmod 17 $.
â€“Â Martin R
1 hour ago

@MartinR Right, in my own code I was using double. I think I fixed all your points now.
â€“Â Simon Forsbergâ™¦
1 hour ago

@aventurin Yeah I was fooled by the modulo requirement, but indeed it goes wrong because the value will be multiplied in the next iteration. Fixed that issue now.
â€“Â Simon Forsbergâ™¦
1 hour ago

@SimonForsberg: Actually it is possible, but you have to multiply with the Ã¢Â€Âœmodular inverseÃ¢Â€Â of (i+1) instead of dividing by (i+1). (C code here: stackoverflow.com/a/35229199/1187415)
â€“Â Martin R
1 hour ago

Â |Â
show 1 more comment

up vote
1
down vote

I have the following questions with regards to the above code:

Is there a smarter way to approach this question?

How can I improve the space and time complexity of the given question?

Have I gone too overboard by using BigInteger Library for this question?

Yes, as follows, and yes. Consider

Modulus your output to 10^9+7

You seem to have taken that instruction rather literally. Multiplication is not constant time when you're working with BigInteger. If all of the multiplications are carried out instead in longs modulo M=10^9+7 then they become effectively constant time.

This gives you two main options:

Compute the two values you currently compute, modulo M, and then use extended Euclid to compute a multiplicative inverse M (which is prime by design) to perform the division.

Use a simple sieve to compute the prime factorisation of each number up to n; then find the power of each prime independently as $nu_p left(binomnrright) = nu_p (n) - nu_p(r) - nu_p(n-r)$. Finally multiply together the appropriate prime powers modulo M.

edited 1 hour ago

answered 1 hour ago

Peter Taylor

14.5k2454

add a commentÂ |Â

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f204574%2fbinomial-coefficient-in-java%23new-answer', 'question_page');

);

Post as a guest

Name

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

up vote
1
down vote

Given the product formula

$$binom nk = prod_i=1^k fracn-k+ii tag1$$

and the symmetry property

$$binom nk = binom nn-k tag2$$

of the binomial coefficient, you can implement the calculation in the following way which avoids fractional intermediate values as well as looping more than $lfloor fracn2rfloor$ times.

public static BigInteger calcBinCoeff(BigInteger n, BigInteger k)

 BigInteger bin; // binomial coefficient
 BigInteger nom; // nominator
 BigInteger den; // denominator

 if (k.shiftLeft(1).compareTo(n) == 1)
 return calcBinCoeff(n, n.subtract(k)); // (2)

 bin = BigInteger.ONE;
 nom = n;
 den = BigInteger.ONE;

 while (den.compareTo(k) < 1) // (1)
 
 bin = bin.multiply(nom).divide(den);
 nom = nom.subtract(BigInteger.ONE);
 den = den.add(BigInteger.ONE);
 

 return bin;

Using long would overflow for $1000 choose 500$.

answered 1 hour ago

aventurin

25017

I've overread the 10^9+7 modulus. With than limitation you could actually use long as @MartinR pointed out in another comment.
â€“Â aventurin
50 mins ago

add a commentÂ |Â

up vote
1
down vote

Given the product formula

$$binom nk = prod_i=1^k fracn-k+ii tag1$$

and the symmetry property

$$binom nk = binom nn-k tag2$$

of the binomial coefficient, you can implement the calculation in the following way which avoids fractional intermediate values as well as looping more than $lfloor fracn2rfloor$ times.

public static BigInteger calcBinCoeff(BigInteger n, BigInteger k)

 BigInteger bin; // binomial coefficient
 BigInteger nom; // nominator
 BigInteger den; // denominator

 if (k.shiftLeft(1).compareTo(n) == 1)
 return calcBinCoeff(n, n.subtract(k)); // (2)

 bin = BigInteger.ONE;
 nom = n;
 den = BigInteger.ONE;

 while (den.compareTo(k) < 1) // (1)
 
 bin = bin.multiply(nom).divide(den);
 nom = nom.subtract(BigInteger.ONE);
 den = den.add(BigInteger.ONE);
 

 return bin;

Using long would overflow for $1000 choose 500$.

answered 1 hour ago

aventurin

25017

I've overread the 10^9+7 modulus. With than limitation you could actually use long as @MartinR pointed out in another comment.
â€“Â aventurin
50 mins ago

add a commentÂ |Â

up vote
1
down vote

Given the product formula

$$binom nk = prod_i=1^k fracn-k+ii tag1$$

and the symmetry property

$$binom nk = binom nn-k tag2$$

of the binomial coefficient, you can implement the calculation in the following way which avoids fractional intermediate values as well as looping more than $lfloor fracn2rfloor$ times.

public static BigInteger calcBinCoeff(BigInteger n, BigInteger k)

 BigInteger bin; // binomial coefficient
 BigInteger nom; // nominator
 BigInteger den; // denominator

 if (k.shiftLeft(1).compareTo(n) == 1)
 return calcBinCoeff(n, n.subtract(k)); // (2)

 bin = BigInteger.ONE;
 nom = n;
 den = BigInteger.ONE;

 while (den.compareTo(k) < 1) // (1)
 
 bin = bin.multiply(nom).divide(den);
 nom = nom.subtract(BigInteger.ONE);
 den = den.add(BigInteger.ONE);
 

 return bin;

Using long would overflow for $1000 choose 500$.

answered 1 hour ago

aventurin

25017

Given the product formula

$$binom nk = prod_i=1^k fracn-k+ii tag1$$

and the symmetry property

$$binom nk = binom nn-k tag2$$

of the binomial coefficient, you can implement the calculation in the following way which avoids fractional intermediate values as well as looping more than $lfloor fracn2rfloor$ times.

public static BigInteger calcBinCoeff(BigInteger n, BigInteger k)

 BigInteger bin; // binomial coefficient
 BigInteger nom; // nominator
 BigInteger den; // denominator

 if (k.shiftLeft(1).compareTo(n) == 1)
 return calcBinCoeff(n, n.subtract(k)); // (2)

 bin = BigInteger.ONE;
 nom = n;
 den = BigInteger.ONE;

 while (den.compareTo(k) < 1) // (1)
 
 bin = bin.multiply(nom).divide(den);
 nom = nom.subtract(BigInteger.ONE);
 den = den.add(BigInteger.ONE);
 

 return bin;

Using long would overflow for $1000 choose 500$.

answered 1 hour ago

aventurin

25017

answered 1 hour ago

aventurin

25017

answered 1 hour ago

aventurin

25017

answered 1 hour ago

aventurin

25017

I've overread the 10^9+7 modulus. With than limitation you could actually use long as @MartinR pointed out in another comment.
â€“Â aventurin
50 mins ago

add a commentÂ |Â

I've overread the 10^9+7 modulus. With than limitation you could actually use long as @MartinR pointed out in another comment.
â€“Â aventurin
50 mins ago

I've overread the 10^9+7 modulus. With than limitation you could actually use long as @MartinR pointed out in another comment.
â€“Â aventurin
50 mins ago

add a commentÂ |Â

up vote
1
down vote

Is there a smarter way to approach this question?

We'll see in a moment. Parts of it can be improved for sure.

How can I improve the space and time complexity of the given question?

You can't. The complexity will remain the same. The changes you can make might give small increases in performance or decrease memory usage, but the complexity will remain the same.

Have I gone too overboard by using BigInteger Library for this question?

I thought at first that it was possible to use just long, but I'm afraid not. Because of 1000 nCr 500, and such big numbers, you are stuck with BigInteger.

You can use BigInteger.valueOf instead of using the constructor with a String.

You can save some time by using the symmetric property of nCr if r > n / 2. For example, 100 nCr 80 is the same as 100 nCr 20.

You can use just one for-loop instead of two:

value = 1;
for (int i = 0; i < r; i++) 
 value = value * (n - i) / (i + 1);

return value;

I used something similar in a project of mine (where I used double instead and thus didn't have to think about truncating integers - an issue which is fixed above thanks to Martin R).

edited 1 hour ago

answered 2 hours ago

Simon Forsbergâ™¦

48.2k7126285

Yes, 1000 choose 500 will overflow with long.
â€“Â aventurin
1 hour ago

1

It should be value = value * (n - i) / (i + 1); so that the intermediate results are integers. But reducing value = value % M in each step could still produce a wrong result, try it with $ binom 103 bmod 17 $.
â€“Â Martin R
1 hour ago

@MartinR Right, in my own code I was using double. I think I fixed all your points now.
â€“Â Simon Forsbergâ™¦
1 hour ago

@aventurin Yeah I was fooled by the modulo requirement, but indeed it goes wrong because the value will be multiplied in the next iteration. Fixed that issue now.
â€“Â Simon Forsbergâ™¦
1 hour ago

@SimonForsberg: Actually it is possible, but you have to multiply with the Ã¢Â€Âœmodular inverseÃ¢Â€Â of (i+1) instead of dividing by (i+1). (C code here: stackoverflow.com/a/35229199/1187415)
â€“Â Martin R
1 hour ago

Â |Â
show 1 more comment

up vote
1
down vote

Is there a smarter way to approach this question?

We'll see in a moment. Parts of it can be improved for sure.

How can I improve the space and time complexity of the given question?

You can't. The complexity will remain the same. The changes you can make might give small increases in performance or decrease memory usage, but the complexity will remain the same.

Have I gone too overboard by using BigInteger Library for this question?

I thought at first that it was possible to use just long, but I'm afraid not. Because of 1000 nCr 500, and such big numbers, you are stuck with BigInteger.

You can use BigInteger.valueOf instead of using the constructor with a String.

You can save some time by using the symmetric property of nCr if r > n / 2. For example, 100 nCr 80 is the same as 100 nCr 20.

You can use just one for-loop instead of two:

value = 1;
for (int i = 0; i < r; i++) 
 value = value * (n - i) / (i + 1);

return value;

I used something similar in a project of mine (where I used double instead and thus didn't have to think about truncating integers - an issue which is fixed above thanks to Martin R).

edited 1 hour ago

answered 2 hours ago

Simon Forsbergâ™¦

48.2k7126285

Yes, 1000 choose 500 will overflow with long.
â€“Â aventurin
1 hour ago

1

It should be value = value * (n - i) / (i + 1); so that the intermediate results are integers. But reducing value = value % M in each step could still produce a wrong result, try it with $ binom 103 bmod 17 $.
â€“Â Martin R
1 hour ago

@MartinR Right, in my own code I was using double. I think I fixed all your points now.
â€“Â Simon Forsbergâ™¦
1 hour ago

@aventurin Yeah I was fooled by the modulo requirement, but indeed it goes wrong because the value will be multiplied in the next iteration. Fixed that issue now.
â€“Â Simon Forsbergâ™¦
1 hour ago

@SimonForsberg: Actually it is possible, but you have to multiply with the Ã¢Â€Âœmodular inverseÃ¢Â€Â of (i+1) instead of dividing by (i+1). (C code here: stackoverflow.com/a/35229199/1187415)
â€“Â Martin R
1 hour ago

Â |Â
show 1 more comment

up vote
1
down vote

Is there a smarter way to approach this question?

We'll see in a moment. Parts of it can be improved for sure.

How can I improve the space and time complexity of the given question?

You can't. The complexity will remain the same. The changes you can make might give small increases in performance or decrease memory usage, but the complexity will remain the same.

Have I gone too overboard by using BigInteger Library for this question?

I thought at first that it was possible to use just long, but I'm afraid not. Because of 1000 nCr 500, and such big numbers, you are stuck with BigInteger.

You can use BigInteger.valueOf instead of using the constructor with a String.

You can save some time by using the symmetric property of nCr if r > n / 2. For example, 100 nCr 80 is the same as 100 nCr 20.

You can use just one for-loop instead of two:

value = 1;
for (int i = 0; i < r; i++) 
 value = value * (n - i) / (i + 1);

return value;

I used something similar in a project of mine (where I used double instead and thus didn't have to think about truncating integers - an issue which is fixed above thanks to Martin R).

edited 1 hour ago

answered 2 hours ago

Simon Forsbergâ™¦

48.2k7126285

Is there a smarter way to approach this question?

We'll see in a moment. Parts of it can be improved for sure.

How can I improve the space and time complexity of the given question?

You can't. The complexity will remain the same. The changes you can make might give small increases in performance or decrease memory usage, but the complexity will remain the same.

Have I gone too overboard by using BigInteger Library for this question?

I thought at first that it was possible to use just long, but I'm afraid not. Because of 1000 nCr 500, and such big numbers, you are stuck with BigInteger.

You can use BigInteger.valueOf instead of using the constructor with a String.

You can save some time by using the symmetric property of nCr if r > n / 2. For example, 100 nCr 80 is the same as 100 nCr 20.

You can use just one for-loop instead of two:

value = 1;
for (int i = 0; i < r; i++) 
 value = value * (n - i) / (i + 1);

return value;

I used something similar in a project of mine (where I used double instead and thus didn't have to think about truncating integers - an issue which is fixed above thanks to Martin R).

edited 1 hour ago

answered 2 hours ago

Simon Forsbergâ™¦

48.2k7126285

edited 1 hour ago

answered 2 hours ago

Simon Forsbergâ™¦

48.2k7126285

answered 2 hours ago

Simon Forsbergâ™¦

48.2k7126285

answered 2 hours ago

Simon Forsbergâ™¦

48.2k7126285

Yes, 1000 choose 500 will overflow with long.
â€“Â aventurin
1 hour ago

1

It should be value = value * (n - i) / (i + 1); so that the intermediate results are integers. But reducing value = value % M in each step could still produce a wrong result, try it with $ binom 103 bmod 17 $.
â€“Â Martin R
1 hour ago

@MartinR Right, in my own code I was using double. I think I fixed all your points now.
â€“Â Simon Forsbergâ™¦
1 hour ago

@aventurin Yeah I was fooled by the modulo requirement, but indeed it goes wrong because the value will be multiplied in the next iteration. Fixed that issue now.
â€“Â Simon Forsbergâ™¦
1 hour ago

@SimonForsberg: Actually it is possible, but you have to multiply with the Ã¢Â€Âœmodular inverseÃ¢Â€Â of (i+1) instead of dividing by (i+1). (C code here: stackoverflow.com/a/35229199/1187415)
â€“Â Martin R
1 hour ago

Â |Â
show 1 more comment

Yes, 1000 choose 500 will overflow with long.
â€“Â aventurin
1 hour ago

1

It should be value = value * (n - i) / (i + 1); so that the intermediate results are integers. But reducing value = value % M in each step could still produce a wrong result, try it with $ binom 103 bmod 17 $.
â€“Â Martin R
1 hour ago

@MartinR Right, in my own code I was using double. I think I fixed all your points now.
â€“Â Simon Forsbergâ™¦
1 hour ago

@aventurin Yeah I was fooled by the modulo requirement, but indeed it goes wrong because the value will be multiplied in the next iteration. Fixed that issue now.
â€“Â Simon Forsbergâ™¦
1 hour ago

@SimonForsberg: Actually it is possible, but you have to multiply with the Ã¢Â€Âœmodular inverseÃ¢Â€Â of (i+1) instead of dividing by (i+1). (C code here: stackoverflow.com/a/35229199/1187415)
â€“Â Martin R
1 hour ago

Yes, 1000 choose 500 will overflow with long.
â€“Â aventurin
1 hour ago

It should be value = value * (n - i) / (i + 1); so that the intermediate results are integers. But reducing value = value % M in each step could still produce a wrong result, try it with $ binom 103 bmod 17 $.
â€“Â Martin R
1 hour ago

@MartinR Right, in my own code I was using double. I think I fixed all your points now.
â€“Â Simon Forsbergâ™¦
1 hour ago

@aventurin Yeah I was fooled by the modulo requirement, but indeed it goes wrong because the value will be multiplied in the next iteration. Fixed that issue now.
â€“Â Simon Forsbergâ™¦
1 hour ago

@SimonForsberg: Actually it is possible, but you have to multiply with the Ã¢Â€Âœmodular inverseÃ¢Â€Â of (i+1) instead of dividing by (i+1). (C code here: stackoverflow.com/a/35229199/1187415)
â€“Â Martin R
1 hour ago

Â |Â
show 1 more comment

up vote
1
down vote

I have the following questions with regards to the above code:

Is there a smarter way to approach this question?

How can I improve the space and time complexity of the given question?

Have I gone too overboard by using BigInteger Library for this question?

Yes, as follows, and yes. Consider

Modulus your output to 10^9+7

This gives you two main options:

Compute the two values you currently compute, modulo M, and then use extended Euclid to compute a multiplicative inverse M (which is prime by design) to perform the division.

Use a simple sieve to compute the prime factorisation of each number up to n; then find the power of each prime independently as $nu_p left(binomnrright) = nu_p (n) - nu_p(r) - nu_p(n-r)$. Finally multiply together the appropriate prime powers modulo M.

edited 1 hour ago

answered 1 hour ago

Peter Taylor

14.5k2454

add a commentÂ |Â

up vote
1
down vote

I have the following questions with regards to the above code:

Is there a smarter way to approach this question?

How can I improve the space and time complexity of the given question?

Have I gone too overboard by using BigInteger Library for this question?

Yes, as follows, and yes. Consider

Modulus your output to 10^9+7

This gives you two main options:

Compute the two values you currently compute, modulo M, and then use extended Euclid to compute a multiplicative inverse M (which is prime by design) to perform the division.

Use a simple sieve to compute the prime factorisation of each number up to n; then find the power of each prime independently as $nu_p left(binomnrright) = nu_p (n) - nu_p(r) - nu_p(n-r)$. Finally multiply together the appropriate prime powers modulo M.

edited 1 hour ago

answered 1 hour ago

Peter Taylor

14.5k2454

add a commentÂ |Â

up vote
1
down vote

I have the following questions with regards to the above code:

Is there a smarter way to approach this question?

How can I improve the space and time complexity of the given question?

Have I gone too overboard by using BigInteger Library for this question?

Yes, as follows, and yes. Consider

Modulus your output to 10^9+7

This gives you two main options:

Compute the two values you currently compute, modulo M, and then use extended Euclid to compute a multiplicative inverse M (which is prime by design) to perform the division.

Use a simple sieve to compute the prime factorisation of each number up to n; then find the power of each prime independently as $nu_p left(binomnrright) = nu_p (n) - nu_p(r) - nu_p(n-r)$. Finally multiply together the appropriate prime powers modulo M.

edited 1 hour ago

answered 1 hour ago

Peter Taylor

14.5k2454

I have the following questions with regards to the above code:

Is there a smarter way to approach this question?

How can I improve the space and time complexity of the given question?

Have I gone too overboard by using BigInteger Library for this question?

Yes, as follows, and yes. Consider

Modulus your output to 10^9+7

This gives you two main options:

Compute the two values you currently compute, modulo M, and then use extended Euclid to compute a multiplicative inverse M (which is prime by design) to perform the division.

Use a simple sieve to compute the prime factorisation of each number up to n; then find the power of each prime independently as $nu_p left(binomnrright) = nu_p (n) - nu_p(r) - nu_p(n-r)$. Finally multiply together the appropriate prime powers modulo M.

edited 1 hour ago

answered 1 hour ago

Peter Taylor

14.5k2454

edited 1 hour ago

answered 1 hour ago

Peter Taylor

14.5k2454

answered 1 hour ago

Peter Taylor

14.5k2454

answered 1 hour ago

Peter Taylor

14.5k2454

add a commentÂ |Â

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Search This Blog

Iyfjky