Easy solution O(n)

  • 0

    This question should be marked "Easy" :-).

    No need for binary search. Here is a simple 2 liner. Since the array is sorted, the duplicate should occur at an odd index. To find it, just check every consecutive pairs until there is a mismatch.

    public int singleNonDuplicate(int[] nums) {
        for(int i = 1; i < nums.length; i+=2) if(nums[i] != nums[i-1]) return nums[i-1];
        return nums[nums.length-1];

    Here is a one liner :-)
    This is based on the fact that xor is commutative, associative and xoring the same number twice cancels each other.

    import java.util.stream.*;
    public int singleNonDuplicate(int[] nums) {
        return IntStream.of(nums).reduce( (a, b) -> a ^ b ).orElse(0);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.