Simple O(n) time and O(1) space


#1

int Solution::repeatedNumber(const vector &A)
{
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
int ele1=A[0],c1=1;
int ele2=0,c2=0;
for(int i=1;i<A.size();i++)
{
if(A[i]==ele1)
{
c1++;
}
else if(A[i]==ele2)
{
c2++;
}
else if(c1==0)
{
ele1=A[i];
c1=1;
}
else if(c2==0)
{
ele2=A[i];
c2=1;
}
else
{
c1–;
c2–;
}
}
c1=0;c2=0;
for(int i=0;i<A.size();i++)
{
if(A[i]==ele1)
c1++;
if(A[i]==ele2)
c2++;
}
int res=0;
if(c1 > A.size()/3)
return ele1;
if(c2>A.size()/3)
return ele2;
return -1;
}