Test by Bikram | Mock GATE | Test 4 | Question: 16

Question

Consider a sorted array of $k+1$ elements, where the elements are first $k$ natural numbers $-\left \{ 1, 2, 3, 4, 5,\dots, k \right \}$ and any one of those $k$ numbers is repeated. The time complexity of best algorithm to find that repeated number is:

• A. $O\left ( k \right )$
• B. $O\left ( k\log k \right )$
• C. $O\left ( \log k \right )$
• D. $O(1)$

Comments

Solution please ?

---

can someone please explain solution properly

@Shaik Masthan

@Bikram sir

---

https://www.geeksforgeeks.org/find-repeating-element-sorted-array-size-n/

Binary search :-

1- Middle number is repeated (middle-> left == middle OR middle->right == middle)
2- If not then check if the middle element is at proper position if yes then start searching repeating element in right.
3- Otherwise the repeating one will be in left.

Answer 1

it can be done in O(logk)

i am writing small pseudo code with function 'algo'

algo(array,k)
{
  if(array[k/2] isduplicate) return k/2; /*isduplicate can be checked in O(1) */

  else if(array[k/2]==k/2 && notduplicate) return algo(right_half array,k/2);

  else if(array[k/2]!=k/2 && notduplicate) return algo(left_half array,k/2);

}

u can see at each iteration we are throwing away half array, so

T(k) = T(k/2) + O(1) 

T(k) = O(logk)

Comments

isduplicate can be checked in O(1)

How ?

---

isduplicate  can be checked  in O(1) for checking it we ill see its left and right neighbor then it is duplicate

so complete algo will take O(logk) time