Time limit exceeded due to the massive elements in the testing array.


  • 1
    Y
    class Solution {
       public static int singleNumber(int[] A) {	
             int i = 0;
             int j = 0;
    	for (  i = 0; i<A.length; i++){
    		for ( j = 0; j<A.length; j++){
    			if ((A[i]==A[j])&&(i!=j)){
    			break;}
    		}
    		if (j==A.length){
    			break;
    		}
    	}
    	return A[i];
      }
    };
    

    This is my solution. It can come out the correct result. However the only thing is time limit exceeded. I know this is because of the system using a very large size of array to test my code. I guess the elements in the array even more than 2^32. So it cause the problem. Does it means this is an incorrect approach to solve the problem? Or can I just go this approach and modified a little bit can be done?


  • 3
    V

    It is certainly the correct approach as it gives right output when executed with the corresponding input but in the question it is mentioned that the algorithm should be of linear time complexity but above algorithm runs in O(n^2).

    O(n^2) time complexity algorithm takes high amount of time compared to linear time algorithm which resulted in TLE. Modify this approach by using bit manipulation which runs in linear time.

    class Solution {
       public static int singleNumber(int[] A) {    
            int result=A[0];
            for(int i=1;i<A.length;i++)
            {
                result= result^A[i];  /* Get the xor of all elements */
            }
            return result;
    }
    }
    

  • 0
    H

    Could you explain this solution a bit: why using the result = result ^ A[i] can reach the goal?


  • 0
    V

    When a number is xored with itself it results in 0. In the question every number except one number occurs twice hence after xoring all the numbers only the single number remains.


Log in to reply
 

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