Find Odd Occurring Element in a Sorted Array in O(logn*logn) Time | #Algorithms #InterviewQuestions

Find Odd Occurring Element in a Sorted Array in O( (logn)^2 ) Time :
Given "n" numbers in a Sorted Array where every number is repeated even number of times except one number which is repeated odd number of times. Find the time complexity of best algorithm to find the number which is repeated odd number of times?

#InterviewPreparation #ComputerScience #GATE2023 #GateCSE #coding #competitivecoding #codingquestions #interviewquestions

Crack #GATE Computer science exam with the best.

Join GO Classes Telegram channel for GATE CSE Doubt Discussion :

Join GATE Overflow Telegram channel for GATE CSE Doubt Discussions :

Join GO Classes Telegram channel for Resources and Announcements :


Complete #C_Programming Course(FREE) Link :

Feel free to contact us for any query.

GO Classes Contact : ([phone]

GO Classes Mail ID :

#gateexam #gate2022 #gatecomputerscience #goclasses #gateoverflow #gate2023exam #algorithms #datastructures #theoryofcomputation #clanguage #operatingsystem #linearalgebra #probability #digitallogic #discretemathematics #dbms #compilerdesign #computernetwork #computerorganisation #computerarchitecture #engineeringmathematics #aptitude #interviewpreparation #coding #competitivecoding #codingquestions #interviewquestions #codingpreparation #programming #programmingquestions #programmingpreparation #programmingchallenge #competitiveprogramming

[GOClassesforGATECS]

Learn, Understand, Discuss.
"GO" for the Best GATE CSE Preparation.

Enroll Now for Goclasses

Enroll Now for GATE CSE 2023 #Test_Series:

[Deepak-qfyz]

At time 1:09, output would be 4, as element 4 is occurring odd number of times.
But Excellent explanation. Thank you for this.

[SAMARPITABHAUMIK]

but sir are you sure when we are finding the range..we are using binary search...but how can u be sure that in the left part binary search it will return the index of left most part...basically we know in binary search when the search is successful it will return....i think linear search will be the better option...bcz we can't assure that by doing binary search we will get left most or right most index ?

[remedyiq]

I have a better approach to this question... Using unordered_map<int, int>
just store all the elements on the map... i.e no and frequency

// it is given one element are odd no times(given)

scan the frequency of unordered map....if the frequency is not divisible by 2 means....it has odd no time.
hence you got the result in o(1) time but space is o(n).

[SAMARPITABHAUMIK]

sir how can you be sure that array is getting divided in two equal halves only bcz it might happen
T(n)=T(n-1)+2lgn, this can be the case that case it will be O(n lgn) not O(lgn *lgn)