Title: Missing Number Source: leetcode.com
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?
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/* https://leetcode.com/problems/missing-number/ */ class MissingNumber { public static void main(String args[]) { MissingNumber solution = new MissingNumber(); int[] nums = {0, 1, 2}; System.out.println(solution.missingNumber(nums)); } public int missingNumber(int[] nums) { int sum = 0; int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int num:nums) { sum += num; if(num > max) max = num; if(num < min) min = num; } if(min!=0) return 0; else if((max-min)==nums.length-1) return max+1; //System.out.println("min: "+min+ " max: "+ max); int actual_sum = ((max + min)*(nums.length+1))/2; //System.out.println("actual_sum: "+ actual_sum); return (actual_sum - sum); } } |