Time complexity 14

Is it 0(n)

No

binary search O(logn)

Accha HAa sorry we can reduce it to O(logn) making changes in binary search...

N^2 is the answer

It cant be n^2... As we can use efficient method having O(logn) to find x

totally wrong answer given

How can we use binary search

We can modify it using odd and even places concept... Where we can use mid value to find if x is on left side or right...

But every element repaet two times

@deepali

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

i.e. go to 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

But in question every element repeat two times

Binary search is not possible.

How will you know what is that element x?
Which way will you move to the right or to the left after selecting the mid element?

 

This might help:

https://www.geeksforgeeks.org/find-element-appears-array-every-element-appears-twice/

this should be done in O(log n) with concept of Binary Search...

I don't know how this method is missing in GFG.

I don't think GFG missed anything.

Try to understand this:

In binary search

"How will you know what is that element x?
Which way will you move? To the right or to the left after selecting the mid element?"

@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.