Modified Binary Search

-
This problem by LeetCode requires a slight modification in a Binary Search algorithm, here is the problem: https://leetcode.com/problems/single-element-in-a-sorted-array/description/:

Given a sorted array consisting of only integers where every element appears twice except for one element which appears 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.
The highlighted note pretty much gives away the approach that should be used: binary search. The difference is that we'll have to make some calculations in order to decide which direction to go in the search. A binary search will look for the middle of the array and make a decision based on its value. In our case we want to compare the middle element with its successor and potentially predecessor. If the middle element is equal its successor, then there is a further calculation: we need to see if the right part of the array is even or odd. Depending on that, and knowing that the current element is equal to its successor, then you make a conscious decision about what way to go. Similar case if the element is equal to its predecessor. Do that, mix it up well, and you will have a nice O(Log(n))-time algorithm using O(1)-space. Code is down below.

By the way, did you notice the new, modern and elegant header for Bing? :)



public class Solution
{
public int SingleNonDuplicate(int[] nums)
{
int l = 0;
int r = nums.Length;
int retVal = -1;
while (l <= r)
{
int m = (l + r) / 2;

 if (m - 1 >= 0 && nums[m] == nums[m - 1])
{
if (m % 2 == 0)
{
r = m - 1;
}
else
{
l = m + 1;
}
}
else if (m + 1 < nums.Length && nums[m] == nums[m + 1])
{
if ((nums.Length - m) % 2 == 0)
{
r = m - 1;
}
else
{
l = m + 1;
}
}
else
{
retVal = nums[m];
break;
}
}

 return retVal;
}
}



Comments

  1. TarasNovember 26, 2017 at 10:26 PM

    Very nice, Marcelo! Interestingly the test cases for this problem seem to perform about the same when using a famous xor based linear solution for this problem, but rules are rules so here is my O(logN) solution:

    class Solution {
    public:
    int singleNonDuplicate(const vector& nums) {
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
    int middle = left + (right - left) / 2;
    int left_count = middle;
    if (middle - 1 >= 0 && nums[middle-1] == nums[middle]) left_count -= 1;
    bool other_than_left = middle - 1 < 0 || nums[middle-1] != nums[middle];
    bool other_than_right = middle + 1 > nums.size() || nums[middle+1] != nums[middle];
    if (other_than_left && other_than_right) return nums[middle];
    if (left_count % 2 == 1) {
    right = middle - 1;
    } else {
    left = middle + 1;
    }
    }
    return -1;
    }
    };

    It's ugly, but it works :D

    Have a splendid rest of the weekend!

    ReplyDelete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more

Hard Leetcode Problem: Grid Illumination

-
Image
Here is the problem:  https://leetcode.com/problems/grid-illumination/ On a  N x N  grid of cells, each cell  (x, y)  with  0 <= x < N  and  0 <= y < N  has a lamp. Initially, some number of lamps are on.   lamps[i]  tells us the location of the  i -th lamp that is on.  Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals ( similar to a Queen in chess ). For the i-th query  queries[i] = (x, y) , the answer to the query is 1 if the cell (x, y) is illuminated, else 0. After each query  (x, y)  [in the order given by  queries ], we turn off any lamps that are at cell  (x, y)  or are adjacent 8-directionally (ie., share a corner or edge with cell  (x, y) .) Return an array of answers.  Each value  answer[i]  should be equal to the answer of the  i -th query  queries[i] . Example 1: Input: N = 5 , lamps = [[0,0],[4,4]] , queries = [[1,1],[1,0]] Output: [1,0] Explanation: Before performing the first query we have both lamps [0
Read more