I stole this problem from Mike Clancy of UC-Berkeley who gave it to me on a flight to a SIGCSE conference. When you become a CS teacher, you learn to travel 3000 miles to talk to people who normally live within a 50-mile radius. It's just how it works. Don't question the genius of it.

Suppose you have an array of N unsorted ints. In the array, all of the numbers 1, 2, ..., N-1 are present. One of the numbers is duplicated in the array.

Given the code, below, write the code for the method findDuplicate that finds the duplicate value in the array WITHOUT USING ANY ADDITIONAL VARIABLES. To be perfectly clear, an index variable is a variable. No additional variables means just that: none, zero, nada, zilch, absence of, etc.

Hint: Draw a picture.

	public static void main(String[] args) {
		int[] arr = new int[10];   // 10 is arbitrary, makes for nice output
		populate(arr);
		printArray(arr);
		System.out.println(findDuplicate(arr));
	}

	private static void populate(int[] arr) {
		Randp rand = new Randp(arr.length);
		for (int i = 0; i < arr.length; i++) {
			arr[i] = rand.nextInt();
			if (arr[i] == arr.length) {
				arr[i] = (int) (Math.random() * (arr.length - 1)) + 1;
			}
		}
	}

	private static int findDuplicate(int[] arr) {
		// YOUR CODE HERE
	}
	
	public static void printArray(int[] arr) {
		for (int i : arr) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	public static void swap(int[] nums2, int index1, int index2) {
		int temp = nums2[index1];
		nums2[index1] = nums2[index2];
		nums2[index2] = temp;
	}