C++ solution using O(1) space and O(N) Tc


#1

int Solution::repeatedNumber(const vector &A) {
int c1=0,c2=0;
int a1=0,a2=0;
for(auto i:A)
{
if(c1!=0 && a1==i)
c1++;
else if(c2!=0 && a2==i)
c2++;
else if(c1==0)
{
c1++;
a1=i;
}
else if(c2==0)
{
c2++;
a2=i;
}
else
{
c1–;
c2–;
}
}
c1=0;
c2=0;
for( int i=0;i<A.size();i++)
{
if(A[i]==a1)
c1++;
if(A[i]==a2)
c2++;
}
int k=A.size()/3;
if(c1>k)
return a1;
else if(c2>k)
return a2;
else
return -1;
}