leetcode/problems/src/array/MissingNumber.java at master · KindleBooks66/leetcode · GitHub

29 lines (26 loc) · 813 Bytes

package array;

/**

* Created by gouthamvidyapradhan on 04/07/2017. Given an array containing n distinct numbers taken

* from 0, 1, 2, ..., n, find the one that is missing from the array.

* <p>For example, Given nums = [0, 1, 3] return 2.

* <p>Note: Your algorithm should run in linear runtime complexity. Could you implement it using

* only constant extra space complexity?

public class MissingNumber {

public static void main(String[] args) throws Exception {

int[] nums = {0};

System.out.println(new MissingNumber().missingNumber(nums));

}

public int missingNumber(int[] nums) {

int sum = 0;

int n = nums.length;

for (int num : nums) {

sum += num;

}

int arrSum = (((n + 1)) * n) / 2;

if (arrSum == sum) return 0;

else return arrSum - sum;

}

Expand file tree