A quiz for the bored

[Rooks Forgenal]

It the making of these functions, I ran across an interesting error that I bet beginners run into a LOT!
Why is the "BAD" function going to produce trash and the "GOOD" section fine?
************************************ BAD ************************************

public int nCr(int n, int r) {
	int answer = 1;
	if (r > n) {
		throw new ArithmeticException(n + "C" + r + " is not valid input.");
	} else if (r == 0 || n == r || n == 0) {
		return 1;
	}
	r = (r > n / 2 ? n - r : r);
	for (int i = 0; i < r; i++) {
		answer = answer * ((n - i) / (i + 1)); //  <<----------------------- LOOK HERE!
		if (answer < 0) {
			throw new ArithmeticException("Escaped the bounds of Integer.  Use nCr_long()");
		}
	}
	return answer;
}

************************************ GOOD *************************************

public int nCr(int n, int r) {
	int answer = 1;
	if (r > n) {
		throw new ArithmeticException(n + "C" + r + " is not valid input.");
	} else if (r == 0 || n == r || n == 0) {
		return 1;
	}
	r = (r > n / 2 ? n - r : r);
	for (int i = 0; i < r; i++) {
		answer = (answer * (n - i)) / (i + 1); //  <<----------------------- LOOK HERE!
		if (answer < 0) {
			throw new ArithmeticException("Escaped the bounds of Integer.  Use nCr_long()");
		}
	}
	return answer;
}

The recursive version of this question is this: This is easier to see but harder to understand.
************************************ BAD **************************************

public int nCr_recursive(int n, int r) {
	if (r > n) {
		throw new ArithmeticException(n + "C" + r + " is not valid input.");
	}
	r = (r > n / 2 ? n - r : r);
	if (r == 0) {
		return 1;
	}
	return (nCr_recursive(n, (r - 1)) * ((n - (r - 1)) / r));
}

************************************ GOOD *************************************

public int nCr_recursive(int n, int r) {
	if (r > n) {
		throw new ArithmeticException(n + "C" + r + " is not valid input.");
	}
	r = (r > n / 2 ? n - r : r);
	if (r == 0) {
		return 1;
	}
	return ((nCr_recursive(n, (r - 1)) * (n - (r - 1))) / r);
}

if you are wondering why I did not put:

throw new ArithmeticException("Escaped the bounds of Integer.  Use nCr_long()");

in the recursive one, it is because I couldn't figure out precisely where I would put it and what the effect would be in the recursion.

[Nisha Ganeriwal]

In the "bad" methods, when you write: answer = answer * ((n - i) / (i + 1)); , in the division, you loose precision because when you divide int by int the result is an int and the remainder is lost. But this does not happen in the "good" methods as there the answer*(n-i) is calculated first which is always perfectly divisible by (i+1).

[Rooks Forgenal]

duly impressed sir/maam. duly impressed.

[Nisha Ganeriwal]

In the recursive methods, you can store the value returned by nCr_recursive(..) in a variable, compare it with 0 and throw the exception.

[Rooks Forgenal]

Like this?

public int nCr_recursive(int n, int r) {  
    if (r > n) {  
        throw new ArithmeticException(n + "C" + r + " is not valid input.");  
    }  
    r = (r > n / 2 ? n - r : r);  
    if (r == 0) {  
        return 1;  
    }
    int result = ((nCr_recursive(n, (r - 1)) * (n - (r - 1))) / r);
    if(result < 1) {
        throw new ArithmeticException("Escaped the bounds of Integer.  Use nCr_long()");
    }
    return result;
}

[Rooks Forgenal]

Turns out GOOD is not so good after all. As a result of reading every output, I found an error in the algorithm when nCr(30,15) is submitted. Can anyone see the error?

public int nCr(int n, int r) {  
    int answer = 1;  
    if (r > n) {  
        throw new ArithmeticException(n + "C" + r + " is not valid input.");  
    } else if (r == 0 || n == r || n == 0) {  
        return 1;  
    }  
    r = (r > n / 2 ? n - r : r);  
    for (int i = 0; i < r; i++) {  
        answer = (answer * (n - i)) / (i + 1); //  <<----------------------- LOOK HERE!  
        if (answer < 0) {  
            throw new ArithmeticException("Escaped the bounds of Integer.  Use nCr_long()");  
        }  
    }  
    return answer;  
}

As a hint, here is how I fixed it.

final private int integerMaxValue = Integer.MAX_VALUE;
public int nCr_recursive_preporation(int n, int r) {
	if (r > n) {
		throw new ArithmeticException(n + "C" + r + " is not valid input.");
	}
	r = (r > n / 2 ? (n - r) : r);
	int iresult = nCr_recursive(n, r);
	if (iresult == 0) {
		long useMoreMemoryToAllowMaximumIntReturns = nCr_recursive_long(n, r);
		if (useMoreMemoryToAllowMaximumIntReturns < 1 || useMoreMemoryToAllowMaximumIntReturns > integerMaxValue) {
			throw new ArithmeticException("Escaped the bounds of Integer.  Reduce the size of Integer n to less than " + n);
		} else {
			iresult = (int) useMoreMemoryToAllowMaximumIntReturns;
		}
	}
	return iresult;
}

private int nCr_recursive(int n, int r) {
	if (r == 0) {
		return 1;
	}
	int funcVal = nCr_recursive(n, (r - 1));
	if (funcVal < 1) {
		return 0;
	}
	funcVal = funcVal * (n - (r - 1));
	if (funcVal < 1) {
		return 0;
	}
	funcVal = funcVal / r;
	return funcVal;
}

private long nCr_recursive_long(int n, int r) {
	if (r == 0) {
		return 1;
	}
	long funcVal = nCr_recursive_long(n, (r - 1));
	if (funcVal < 1) {
		return 0;
	}
	funcVal = funcVal * (n - (r - 1));
	if (funcVal < 1) {
		return 0;
	}
	funcVal = funcVal / r;
	return funcVal;
}