# No extra memory

• Most solutions posted use extra memory. In order to avoid this, we make use of the given vector/array. The trick is to remove first three entries of the given array after checking the identity of v[0]. It remains to check whether the element v[0] occurs three times or not; if its occurrence is not 3, return v[0] as we already found the required element. If not, clear the first three elements and proceed using the familiar bit operation.

This solution also requires two additional indexing variables i and j. I think some kind of loop is needed.

``````class Solution {
public:
int singleNumber(vector<int>& v) {
for (int j=1; j<=3; j++)
for (int i=j; i<v.size(); i++)
if(v[0]==v[i]) swap(v[i],v[j]);

if(v[0]!=v[1]||v[0]!=v[2]) return v[0];
if(v[0]==v[3]) return v[0];

v[0]=v[1]=v[2]=0;
for (int i=3; i<v.size(); i++)
v[0]^=v[i],
v[1]|=(v[0]^v[i])&v[i],
v[2]=~(v[0]&v[1]),
v[0]&=v[2],
v[1]&=v[2];
return v[0];
}
};``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.