Hi,
I tried running the solution code for Challenge 1 ( We are given a sorted array of integers, nums , that contain n integers , where each integer is in the range [0,n−1] inclusive. There is only one duplicate number in nums . Find and return this duplicate number.)
but it didn’t return the correct input. Can you please check?
nums = [11,11,12,13,14,15,16]
The result should be 11, but the solution returned is 16.
My bad. I missed the cond: 1≤nums[i]<nums.length
But, what shall be the solution via binary search incase the above condition isn’t given?
Hi @Aditya_V,
Welcome to the Discuss community!
If we see the constraints of this challenge, it clearly says that the value at each index will be in between 1 and the length of the array. Also, there is only one duplicated element in the array. To fulfil these requirements, the provided solution works absolutely fine.
However, we can implement the solution if the second constraint is not present in the solution by considering the first element in account. We can subtract the first element from the values that are being compared to move the pointers. We can update the current solution with the following code:
In C++ solution, update line 14:
In Java solution, update line 11:
In JavaScript solution, update line 10 to
} else if (nums[mid] - nums[0] +1 > mid) {
In Python solution, update line 10 to:
elif nums[mid] - nums[0] +1 > mid:
nums[mid] - nums[0] +1 will make the value in between 1 to length of array in the comparison, and the pointers will move accordingly. Keep remember that the other conditions (especially * All of the integers in nums appear only once, except for one integer that appears twice.) must present in the data to use binary search for this challenge.
I hope you get how to use binary search if this 1≤nums[i]<nums.length condition doesn’t present. If you’ve any other query, do let us know.
Thanks!