- Need to find missing number between 1 to N with low time complexity O(n).
- Step1: Get sum of natural numbers from 1 to N as N x(N+1)/2
- Step2: Get sum of array elements
- Step3: Missing number = natural numbers sum - array sum
FindMissingNumber.java
public class FindMissingNumber {
private static final int END_NUMBER = 10;
private int getMissingNumber(int[] arr) {
int missingNum = 0;
int arrSum = 0;
for (int i = 0; i < arr.length; i++) {
arrSum += arr[i];
}
int naturalSum = END_NUMBER * (END_NUMBER + 1) / 2;
missingNum = naturalSum - arrSum;
return missingNum;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 0, 5, 6, 7, 8, 9, 10};
FindMissingNumber app = new FindMissingNumber();
int missingNum = app.getMissingNumber(arr);
System.out.println("Missing Number = " + missingNum);
}
}
****** OUTPUT ********
Missing Number = 4
******* OUTPUT ********
No comments:
Post a Comment