Time complexity

Question

Given a sorted array of n elements where other than one element x every other element repeat two times. Then how much time will it take to find position of x?

Comments

ok do it

---

It is not required to select mid element in binary search ,u can select 1 element than 2nd element than 4th than 8th so on

---

https://youtu.be/nMGL2vlyJk0

Checkout for clear understanding

Answer 1

Time complexity for this solution is O ( lgn ), you will also find the condition to move left or right here.

see from question I can conclude that array must be of odd length...right

because every element but one is repeated twice, arr[] = 1,1,2,2,3,4,4 --> length = 7

lets start binary search with middle_element_index = floor( 7 / 2 ) = 3

arr[ 3 ] = 2              1,1,2,2,3,4,4

now compare this element with next and previous index element

if arr[3] matched with previous element:       1,1,2,2,3,4,4

           your single element must be on right side of this middle

if arr[3] matched with next element:        

          ( for this condition to satisfy your array must have been like this 1,2,2,3,3,4,4 )

          your single element must be on left side of this middle

else you found that single (bachelor) element who was disturbing other couples  :

find appropriate side to move, find next middle on that side and repeat procedure

until you either reach end, or both next and previous element different, in that case you found single element

Comments

What if I would give input- 1,1,2,2,3,3,4,5,5

---

Plz verify if the following solution gives correct output for all possible inputs
https://gateoverflow.in/47506/time-complexity?show=132923#a132923 .

Answer 2

digvijay sir is right... first thing...repeated...once...means..112233... repeated twice means...111222333....

if(a[i] != a[i+1)  printf(a[i]); /return 1///first element is single...

      else if (a[j) ! =a[j-1]) printf(a[j]); return 1////last element is single...

Bs(a,i,j,n)  ///                where i is the index of first element..j is the index of last element..                                                                                   n is the no. of elements  in array...'a'   is array adddress

if(n%2==0)/////when 'n' is even 

{    

               mid= (i+j)/2 /////take ceil value

             if(a[mid-1) != a[mid] ! && a[mid] != a[mid+1]) printf(a[mid); return 1////mid element is single..

             else if(a[mid) != a[mid +1] ) 

            {  BS(a, mid+1, j,n)  ////move right

              }

            else if(a[mid-1]== a[mid]a && [mid]== a[mid+1])

           {      BS(a, i ,mid-2)  ////move left

              }

}

else/////when n is odd

{

               mid= (i+j)/2 /////

             if(a[mid-1) != a[mid] != a[mid+1]) printf(a[mid); return 1////mid element is single..

             else if(a[mid) != a[mid -1 ) 

            {     BS(a, mid+3, j,n)  ////move right

            }  else if(a[mid) == a[mid -1 ) 

            {     BS(a, i,mid-3,n)  ////move left

            }  

                

}                complexity is 0(logn)  plz..take input and verify and if any error or facing any problem...ask me

Comments

You are checking the mid element to be single- then why do the same again for first element? Also, we cannot compare 3 elements using ==, it should be done using == and &&.

---

oh..yes..i forget..thankyou arjun sir ...we cannot compare using === i will update..it..///and there is little bit...redundency...but..sir u plz check ..my logic..is correct or not...

---

sir check now....tell where m wrong...i have updated it..

Answer 3

let size of array is n and elements in the array are consecutive n-1 integer in which one element is repeated then we can apply Binary Search.

Answer will be O(log n)

Comments

can you give working example ?

---

qus is about every element is repeated two time except one element .

---

yes i also got logn...but manoj...confused me...

---

yes sorry for that .

---

its ok..

---

Is it mentioned that elements in the array are consecutive n-1 integer  ?

If not then how can we find repeated number. ??

---

@Digvijay sir, Can you give me the condition which you are using to take left turn and right turn from middle. How will you know that that single element exist in left side or right side of middle.?

---

@rude sir

I think we can apply binary search

for your example:1,2,2,3,3,4,4,5,5,6,6,7,7,8,8

array indexing is from 0 to 14

so mid index= 0+14/2 which gives 7th index which is 5, now we will move left as 1<5

so again we apply binary search on left array and at last we reach at index 0 which is "1"

so it will be done in 0(logn) time.

---

I suspect that the main confusion about this question lies in the given input....whether x is given in input as we need to find its position(clearly, O(logn)) or we need to find both, the element x and its position in the array(don't think O(logn) possible)?

 

---

we have to find the position that's why we are applying binary search

Answer 4

This is possible in O(lg n) time using Divide and Conquer technique.
Below is a C program for the same  
 

#include <stdio.h>

int findNonRepeated(int arr[], int i, int j);

void main() {
    int arr[] = {10, 20, 20, 30, 30, 50, 50, 60, 60};
    int len = sizeof(arr) / sizeof(arr[0]);
    int x = findNonRepeated(arr, 0, len - 1);
    printf("\n X: %d", x);
}

int findNonRepeated(int arr[], int i, int j) {
    // Base Case
    if (i == j) return arr[i];

    // Divide
    int mid = (i + j) / 2;

    // Conquer
    // If left element equals current element
    if (arr[mid - 1] == arr[mid]) {
        // If current index is even search in left side
        if (mid % 2 == 0)
            return findNonRepeated(arr, i, mid - 2);
        else
            return findNonRepeated(arr, mid + 1, j);
    } else if (arr[mid] == arr[mid + 1]) {
        // If current index is even search in right side
        if (mid % 2 == 0)
            return findNonRepeated(arr, mid + 2, j);
        else
            return findNonRepeated(arr, i, mid - 1);
    } else
        return arr[mid];
}

Comments

This looks good .Can some one find if it misses any case?@Arjun sir ,please check once