package miscellaneous.math.statistics.lc268_missingnumber;

/**
 * Given an array containing n distinct numbers taken from 0, 1, 2, ..., n,
 * find the one that is missing from the array.
 * For example, given nums = [0, 1, 3] return 2.
 * Note: Your algorithm should run in linear runtime complexity.
 * Could you implement it using only constant extra space complexity?
 */
public class Solution {

    // My 2nd
    public int missingNumber(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        // It should be (1 + N) * N / 2
        return (1 + nums.length) * nums.length / 2 - sum;
    }

    // Bit operating solution: same as Single Number
    // Eg.[0,1,3] ^ [0,1,2,4] = 2
    public int missingNumber2(int[] nums) {
        int missing = 0, all = nums.length;
        for (int i = 0; i < nums.length; i++) {
            missing ^= nums[i];
            all ^= i;
        }
        return missing ^ all;
    }

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

}

@@ -394,16 +394,226 @@
 tion %7B%0A%0A
+    // 3AC.%0A    public int missingNumber(int%5B%5D nums) %7B%0A        int missing = 0;%0A        for (int i = 1; i %3C= nums.length; i++) %7B%0A            missing %5E= nums%5Bi - 1%5D %5E i;%0A        %7D%0A        return missing;%0A    %7D%0A%0A
     // M
@@ -638,32 +638,33 @@
 nt missingNumber
+3
 (int%5B%5D nums) %7B%0A 

missing number