Ac solution code


  • 0

    Solution1. Bit manipulation - XOR: O(n) runtime; O(1) space

    As a^b^b = a, by XOR all numbers with its indices, paired (i, nums[i]) should be eliminated, finally we can get the missing number.

    public int missingNumber(int[] nums) {
    	int res = nums.length;// Don't forget to XOR nums.length
    	for (int i = 0; i < nums.length; i++) 
    		res ^= i ^ nums[i];
    	return res; 
    }
    

    Solution2. Math: O(n) runtime; O(1) space

    All (i, nums[i]) should be paired, except one missing number. So missingNumber = sum_indices - sum_values.

    public int missingNumber(int[] nums) {
    	int sum_values = 0, sum_indices = nums.length;
    	for (int i = 0; i < nums.length; i++) { 
    		sum_values += nums[i]; 
    		sum_indices += i;
    	}
    	return sum_indices - sum_values;
    }

Log in to reply
 

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