Problem:- Given a list of number from 1 to N find the missing number ....
Logic -Just calculate sum of N natural numbers (n*(n+1))/2.
Then subtract the sum of all given numbers from above calculated sum and you will get missing number.
here is the code......
public class MissingNumberProblem {
static int missNum;
static int largestNum;
static int naturalSum;
static int totalNumbersSum;
public static void main(String args[]) {
int[] arr = {
4,
2,
6,
5,
3,
1,
8,
12,
9,
11,
7
};
largestNum = findLargestNumber(arr);
naturalSum = (largestNum * (largestNum + 1)) / 2;
for (int i = 0; i < arr.length; i++) {
totalNumbersSum = totalNumbersSum + arr[i];
}
missNum = naturalSum - totalNumbersSum;
System.out.println("Missing number is " + missNum);
}
public static int findLargestNumber(int[] arr) {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
}
return arr[arr.length - 1];
}
}