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


  • 1
    Y

    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];
        }

  • 0
    S

    Could you please detail your question, like tell your brief thought even how you analysis your complexity? not just paste your code without any comment. We encourage to ask good questions for great answer. Thx!


  • 2
    B

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


  • 50
    J

    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];
    }
    };
    

  • 0
    S

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


  • 0
    C

    Can you explain on it?


  • 0
    J

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


  • 0
    G

    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;
        }
    };

  • 0
    X

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


  • 0
    G

    Thanks... updated!


  • 0
    H

    excellent, excellent


  • 6
    S

    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;
        }
    };
    

  • 0
    M

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


Log in to reply
 

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