0(N) time and O(1) space JAVA SOLUTION


  • 1
    Z

    public int missingNumber(int[] nums) {

        int n = nums.length;
        int original = 0;
        int current = 0;
        
        for(int i=0;i<nums.length;i++){
            original+=i;
            current+=nums[i];
        }
        
        return original+n-current;
    }

  • 0
    P

    public int missingNumber(int[] nums) {
    int total = nums.length*(1 + nums.length)/2;
    int sum = 0;
    for(int temp:nums){
    sum += temp;
    }
    return total - sum;
    }


  • 0
    C

    By bit manipulation:

    public int missingNumber(int[] nums) {
        int n = nums.length;
        byte [] fills = n%8 == 0 ? new byte[n/8] : new byte[n/8+1];
        for(int i = 0; i<nums.length; i++){
            int val = nums[i];
            int byteNum =  val / 8;
            int offset = val % 8;
            fills[byteNum] |= 1 << offset;
        }
        int base = 0;
        for(base = 0; base < fills.length ; base++){
            if(fills[base] !=  -1){
                break;
            }
        }
        int offset = 0;
        for(int i = 0; i<8; i++){
            if((fills[base] & (1<<i)) == 0){
                offset = i;
                break;
            }
        }
        return base * 8 + offset;
    
    }

Log in to reply
 

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