Arrays & Hashing
Find missing odd
Given:
- An array of positive integers sorted either ascending or descending.
- The array contains all odd numbers from
mtonexcept for one missing number.
Task:
- Write a Java function to find the missing odd number in the array.
Constraints:
- The array length is between 1 and 100.
- There is always exactly one missing odd number.
public class MissingOddNumber {
public static int findMissingOddNumber(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// Check if the current element is odd
if (nums[mid] % 2 != 0) {
// Calculate the expected next odd number
int expectedNextOdd = nums[mid] + 2;
// Check if the next element is missing
if (mid + 1 < nums.length && nums[mid + 1] != expectedNextOdd) {
return expectedNextOdd;
}
// Move to the right half
left = mid + 1;
} else {
// Move to the left half
right = mid - 1;
}
}
// If the missing number is the first or last element
if (nums[0] != 1) {
return 1;
} else {
return nums[nums.length - 1] + 2;
}
}
public static void main(String[] args) {
int[] nums1 = {1, 3, 5, 7, 9, 13, 15, 17};
int[] nums2 = {9, 7, 3};
System.out.println(findMissingOddNumber(nums1)); // Output: 11
System.out.println(findMissingOddNumber(nums2)); // Output: 5
}
}
