# My answer is not getting accepted because I am exceeding the time limit.

• Can anyone tell me how to write a code which will run with minimum time complexity. Here is the code that I have.

``````public int singleNumber(int[] A) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int i,j;

if (A.length == 0) {
System.out.print(true);
return 0;
}
for (i = 0; i < A.length; i++) {
for (j = i+1; j < A.length-1; j++) {
if (A[i] > A[j]) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
for (i = 0; i < A.length; i++) {
System.out.print(A[i]+" ");
}
i=0; j=i+1;
while (j<A.length){
if (A[i] != A[j]) {
return A[i];
}
i = i + 2;
j = j + 2;
}
return A[i];
}``````

• Your code runs in O(n^2) due to the double loops. It's expected to be in O(n).

• Use operator XOR like this.

Crack the problem in O(n) time complexity without using extra space.

``````class Solution {
public:
int singleNumber(int A[], int n) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
while (--n!=0) A[n-1]^=A[n];
return A[0];
}
};
``````

• O(n^2) still can be accepted. but there is O(n)

• Can you explain on it?

• Since A^A=0, thus we can get the single number like this A^B^A=B.

• A answer that uses some extra memory, at most half of the size of A as half of the numbers are repeated in A. Although it avoids sorting and it faster, the complexity would still be in the `O(cnlogn)` where c should be lesser that 0.5.

``````#include<set>

class Solution {
public:
int singleNumber(int A[], int n) {

std::set<int> b;
std::set<int>::iterator it;
int i;
for(i=0;i<n;i++)
{
it = b.find(A[i]);
if(it!=b.end())
b.erase(it);
else
b.insert(A[i]);
}

it = b.begin();
return *it;
}
};``````

• finding an element in the set is not linear scan. the complexity of finding elements in set is O(log n)

• Thanks... updated!

• excellent, excellent

• This problem can be solved using X-OR operations because (A)^(B)^(A)^(A) = B.

``````class Solution {
public:
int singleNumber(int A[], int n) {
int x = 0;
for(int i = 0;i<n;i++){
x ^= A[i];
}
return x;
}
};
``````

• Check your XORs. You have 3 A in the left side, only 2 actually cancel.

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