@@ -7,6 +7,17 @@ public static void main(String[] args) {
77 assert combinations (10 , 5 ) == 252 ;
88 assert combinations (6 , 3 ) == 20 ;
99 assert combinations (20 , 5 ) == 15504 ;
10+
11+ // Since, 200 is a big number its factorial will go beyond limits of long even when 200C5 can be saved in a long
12+ // variable. So below will fail
13+ // assert combinations(200, 5) == 2535650040l;
14+
15+ assert combinationsOptimized (100 , 0 ) == 1 ;
16+ assert combinationsOptimized (1 , 1 ) == 1 ;
17+ assert combinationsOptimized (10 , 5 ) == 252 ;
18+ assert combinationsOptimized (6 , 3 ) == 20 ;
19+ assert combinationsOptimized (20 , 5 ) == 15504 ;
20+ assert combinationsOptimized (200 , 5 ) == 2535650040l ;
1021 }
1122
1223 /**
@@ -32,4 +43,32 @@ public static long factorial(int n) {
3243 public static long combinations (int n , int k ) {
3344 return factorial (n ) / (factorial (k ) * factorial (n - k ));
3445 }
46+
47+ /**
48+ * The above method can exceed limit of long (overflow) when factorial(n) is larger than limits of long variable.
49+ * Thus even if nCk is within range of long variable above reason can lead to incorrect result.
50+ * This is an optimized version of computing combinations.
51+ * Observations:
52+ * nC(k + 1) = (n - k) * nCk / (k + 1)
53+ * We know the value of nCk when k = 1 which is nCk = n
54+ * Using this base value and above formula we can compute the next term nC(k+1)
55+ * @param n
56+ * @param k
57+ * @return nCk
58+ */
59+ public static long combinationsOptimized (int n , int k ) {
60+ if (n < 0 || k < 0 ) {
61+ throw new IllegalArgumentException ("n or k can't be negative" );
62+ }
63+ if (n < k ) {
64+ throw new IllegalArgumentException ("n can't be smaller than k" );
65+ }
66+ // nC0 is always 1
67+ long solution = 1 ;
68+ for (int i = 0 ; i < k ; i ++) {
69+ long next = (n - i ) * solution / (i + 1 );
70+ solution = next ;
71+ }
72+ return solution ;
73+ }
3574}
0 commit comments