Time complexity 14

Question

Comments

@Registered user 48

check my answer...

I apolize the GFG community, due to the link https://www.geeksforgeeks.org/find-element-appears-array-every-element-appears-twice/   is for unsorted array, without noticing that, i commented GFG misses the approach

---

@srestha, i don't know how you told this

if x is a given element then we can just do a binary search

i.e. go to the middle element and if greater, go to right side otherwise left side

As it is a sorted array binary search is enough to find x.

1.do you know the value of x?

2.yes you can go to middle element okk..but after that ???? how can you say whether i have to go right or left if you don't knw the value of x?

 

think about this these things  once

---

@shaik masthan

 

Yeah, got it. Never approached the problem in terms of number of elements.

Thanks Anyways.

Answer 1

 

in even no.of elements position, one element is single, then there should be exist another element is single, but in the question they mention that every element is twice occurred and only one element is single, Therefore even no.of element positions doesn't have single element

Comments

well explained Shaik Masthan 

Answer 2

answer is O(logn) as the array is sorted and we can apply binary search to find the position of such element. For further knowledge refer https://www.geeksforgeeks.org/find-the-element-that-appears-once-in-a-sorted-array/

Comments

1.do you know the value of x?

2.yes you can go to middle element okk..but after that ???? how can you say whether i have to go right or left if you don't knw the value of x?

Answer 3

answer is O(n) .   Use bitwise XOR manipulation.