TestBook Test Series

Question

there is a sorted array which is of very large. every element is repeated more than once except one element. how much time will it take to find the element?

Comments

well i came up with this solution:let take first element and compare with second if it is equal than increment a count variable and than compare first element with the next one if the next one is not equal to first one than make that element the first and set count as 0 if the next element which is in line have a element not equal to it then the first will be incremented but this time count is a zero value so our program will halt. so this can be done in O(n).

---

Since the array is sorted, we can easily do it in O(n). Traverse the array with index i, compare a[i] with a[i+1] and a[i+1] with a[i+2], if both the comparisons results false(i.e all three are unequal). then a[i+1] is the unique element. Some more details are for extreme ends, when i = 0 and when near the end of array.

Answer 1

o{n}

Comments

please explain

---

and why not O(logn)

---

In binary search complexity is O(logn ) because after visiting middle element you have to go either left or right but in this ques you have to traverse both left and right.

one solution can be using the algo of counting sort find the array B (that represents frequency of elements).{i hope you know about counting sort), then search for 1 in B.

or you can traverse each element linearly and checking if either of its left or right are equal to that element. if not then you have find ur required element.

---

we can not apply binary search because binary search takes key as input so i think only solution is linear search