title: How can I shave .1 seconds from the runtime of this program?
body: <p>I'm working on a practice program at InterviewStreet and I have a solution that runs with a time of 5.15xx seconds, while the maximum time allowed for a java solution is 5 seconds. Is there anything I can do with what I've got here to get it under 5 seconds? There's also a limit of 256 MB so as near as I can tell this is both the most time and memory efficient solution to the problem...</p>
  
  <p>edit:
  The possible values for N and K are N &lt;= 10^9 and K &lt;= N, which is why I chose to do everything using BigInteger.  The maximum number of trials is 10000. So basically, you input the number of trials, then a pair of integer values for each number of trials, and the program computes the three versions of the binomial coefficient for the equation in the second loop. I figured it would be faster to read everything into the arrays, then process the arrays and put the results into a third array to be processed by the third loop because I figured it might be faster that way. I tried doing everything in the same loop and it ran slower.  </p>
  
  <p>I've tried three or four different algorithms for calculating the binomial coefficient (nCr - or n choose r, all are different ways of saying the same thing). Some of the algorithms involve a two dimensional array like c[n][k]. This is the only solution I've submitted that didn't come back with some sort of memory error. The answer needs to be output mod (10 ^ 6) + 3 because the answers of nCr * nCr get pretty huge.  A sample run of the program is:</p>
  
  <pre><code>3
  
  4 1
  5 2
  90 13
  
  2
  5
  815483
  </code></pre>
  
  <p>Can't run it on a faster machine because it needs to pass on their machine to count, basically I submit the code and they run it against their test cases, and I have no idea what their test case is, just that the inputs are within the bounds given above.</p>
  
  <p>And the program itself:</p>
  
  <pre><code>import java.math.BigInteger;
  import java.util.Scanner;
  
  public class Solution {
  
  public BigInteger nCr(int n, int r) {
      if (r &gt; n ) {
          return BigInteger.ZERO;
      }
  
      if (r &gt; n / 2) {
          r = n - r;
      }
      BigInteger result = BigInteger.ONE;
  
      for (int i = 0; i &lt; r; i++) {
          result = result.multiply(BigInteger.valueOf(n - i));
          result = result.divide(BigInteger.valueOf(i + 1));
      }
      return result;
  }
  
  public static void main(String[] args) {
      Scanner input = new Scanner( System.in );
      BigInteger m = BigInteger.valueOf(1000003);
      Solution p = new Solution();
      short T = input.nextShort(); // Number of trials
      BigInteger intermediate = BigInteger.ONE;
      int[] r = new int[T];
      int[] N = new int[T];
      int[] K = new int[T];
  
      short x = 0;
  
      while (x &lt; T) {
      N[x] = input.nextInt();
      K[x] = input.nextInt();
      x++;
      }
  
      x = 0;
      while (x &lt; T) {
      if (N[x] &gt;= 3) { 
              r[x] = ((p.nCr(N[x] - 3, K[x]).multiply(p.nCr(N[x] + K[x], N[x] - 1))).divide(BigInteger.valueOf((N[x] + K[x]))).mod(m)).intValue();
          } else {
              r[x] = 0;
      }
      x++;
      }
  
      x = 0;
      while (x &lt; T) {
      System.out.println(r[x]);
      x++;
      }
  }
  </code></pre>
  
  <p>}</p>