I am writting a code to show the number of ways we can pick k # of objects from n total # of objects, and order them without repetition(n choose k). I am given the recrusive for
public static long tough(int x, int y) {
if (x < y) return tough(y, x);
else if (y <= 0) return 1;
else { if (x>y) return tough(x-1, y) + tough(x-1, y-1);
else return tough(x-1, y-1);}}
We are then asked to write a NON-recursive format, which I already have. My only question is, due to a statement the professor said, is there anyway I can rewrite my non-recursive program so that it uses only ONE for loop, and no other loops, so that it has a time complexity of O(n)? Any help or input advice is greatly appreciated.
import java.util.*;
public class KCombination {
public static void main(String[] args) {
Scanner in1 = new Scanner(System.in);
Scanner in2 = new Scanner(System.in);
System.out.println("Input a number of total objects to choose from: ");
int n = in1.nextInt();
System.out.println("Input a select number of objects to choose from the total number of objects: ");
int k = in1.nextInt();
int difference = (n-k);
for (int i = (n-1); i >= 1; i--) {
n *= i;
}
for (int i = (k-1); i >=1; i--) {
k *= i;
}
for (int i = difference-1; i>=1; i--) {
difference *= i;
}
System.out.println("The factorial value of the first input is: " + n +".");
System.out.println("The factorial value of the first input is: " + k +".");
System.out.println("The factorial value of the first and second input's difference is: " + difference +".");
int combination = n/(k*difference);
System.out.println("The number of ways to order k objects chosen from n total objects, without repetion, is: " + combination +".");
}
}