Solution: Missing Number in Sorted Array
This review discusses the solution of the missing number in a sorted array challenge in detail.
We'll cover the following...
Solution #1
Press + to interact
class MissingNumber {public static int missingNumber(int[] arr, int size) {int missing = -1; // if no element is missingint last = arr[0]; // start off from the first elementif(last != 1){return 1;}for (int i = 1; i < size; i++) { // traverse through the whole arrayif (arr[i] - last > 1) {missing = last + 1;break;}last++;}return missing;}public static void main(String args[]) {int[] input1 = {1,2,4};System.out.println(missingNumber(input1, input1.length));}}
A naive solution to this problem would be:
-
Traverse through the whole list starting from the first index.
-
Find out the difference between the current and the last index element.
-
If the difference is greater than 1, it means the integer between the current and last index is missing.
-
Return
index+1
(as the array is contiguous and starts from 1, the missing number will be equal toindex+1
).
Time complexity
This solution iterates ...
Access this course and 1400+ top-rated courses and projects.