Find a Number

Last Updated on March 25, 2021 by Aniruddha Guin

Concepts Used

Binary Search

Difficulty Level

Easy

Problem Statement :

^{Finding a number has always been an interesting puzzle! Well in this problem we are given a sorted array of some numbers in which every element is present twice except one element. We have to find this element. Easy isn’t it?}

EXAMPLE:

Input
11
1 1 3 3 4 5 5 7 7 8 8
Output
4

You are encouraged to try the problem on your own before looking at the solution.
See original problem statement here

^{We can definitely do this easily in a naïve way by simply searching through the array element by element and check its previous and next elements. But this will take the time complexity to O(n) where n is the number of elements present in the array. We have to think of better approach than simply searching element by element.}

Approach #1

^{Let us first observe a sorted array with such condition and see if we can find anything interesting.}

^{I have also marked e = even and o = odd indexes to see a pattern. Look carefully in the above array the answer is 4 but before it, all the duplicate elements – first element is always at even position and the second element is at odd position but after the answer element first element is at odd position and the second element is at even position.
This gives us an idea that whenever we find that for a current element if the next element is equal to it and the current position is even and the next position is odd that means our answer is not encountered so we can search in the right half else in the left half.
We think of a Binary Search approach for this problem. Let us see the Algorithm.}

Algorithm

1)  Find the mid of the low and high index.
2)  If (low == high) return ans = low.
3)  If the mid element == mid + 1 element and check the index of mid element. If mid is even and mid+1 will be odd. Search in the right of mid else search in the left of mid.
4)  If the mid element == mid - 1 element and check the index of mid element. If mid is even and mid-1 will be odd. Search in the right of mid else search in the left of mid.

ALON

#include 
using namespace std;
void search(vector &arr,int n,int &ans,int l,int r){
  if(l>r)return;
  if(l == r){ans = arr[l]; return;}
  int mid = r + (l-r)/2;
  if(mid%2 == 0){
    if(arr[mid] == arr[mid+1])
      search(arr,n,ans,mid+2,r);
    else
      search(arr,n,ans,l,mid);
  }else{
    if(arr[mid] == arr[mid-1])
      search(arr,n,ans,mid+1,r);
    else
      search(arr,n,ans,l,mid-1);
  }
  return;
}
int main()
{
  //write your code here
  int n;
  cin>>n;
  vector arr(n);
  for(int i = 0;i>arr[i];
  int ans = -1;
  search(arr,n,ans,0,n-1);
  cout<
						 

import java.util.*;
import java.io.*;

public class Main {
  public static int ans = -1;
public static  void search(int[] arr,int n,int l,int r){
  if(l>r)return;
  if(l == r){ans = arr[l]; return;}
  int mid = r + (l-r)/2;
  if(mid%2 == 0){
    if(arr[mid] == arr[mid+1])
      search(arr,n,mid+2,r);
    else
      search(arr,n,l,mid);
  }else{
    if(arr[mid] == arr[mid-1])
      search(arr,n,mid+1,r);
    else
      search(arr,n,l,mid-1);
  }
  return;
}
  public static void main(String args[]) throws IOException {

    //write your code here
    int n;
    Scanner sc =  new Scanner(System.in);
    n = sc.nextInt();
    int[] arr = new int[n];
    for(int i = 0;i
						 

Dry Run

^{Let’s dry run our sample test case –
N = 11}


[forminator_quiz id=”2543″]