May 12, 2020

#LeetCode:Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10

Note: Your solution should run in O(log n) time and O(1) space.

Algorithm:
1). "Every element appears exactly twice, except for one element which appears exactly once." This means length of the array would be always odd.
2). If the length is one, return the first element.
3). We will start iterating the array, by declaring 2 points i & j. Element at ith and jth position will be consecutive.
4). If element at ith position is not equal to element at jth position, return the ith element, else increment the j with 2.
5). If no such element is encountered, we can confidently return the last element in the sorted array (as it will be the one with out a duplicate value).

Java Solution
ALSO CHECKOther LeetCode Solutions in Java

-K Himaanshu Shuklaa.

No comments:

Post a Comment