268. Missing Number.java

/*
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

 

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
Example 4:

Input: nums = [0]
Output: 1
Explanation: n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.
 

Constraints:

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
All the numbers of nums are unique.
*/

//Solution:


//Using Cyclic Sort:
class Solution {
    public int missingNumber(int[] nums) {
        cyclicSort(nums);
        int ele = nums.length;
        for(int i = 0;i<nums.length;i++){
            if(nums[i] != i){
                ele = i;
            }
        }
        return ele;
    }
    
    public void cyclicSort(int[] arr){
        int i = 0;
        while(i < arr.length){
            if(arr[i] == arr.length){
                i++;
            }else if(arr[i] != i){
                swapArray(arr,i,arr[i]);
            }else{
                i++;
            }
        }
    }
    
    public void swapArray(int[] arr,int first,int second){
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
    
}

//Optimized one:
class Solution {
    public int missingNumber(int[] nums) {
        int arraySum = 0;
        int nSum = (nums.length * (nums.length + 1))/2;
        for(int i = 0;i < nums.length;i++){
            arraySum = arraySum + nums[i];
        }
        return nSum - arraySum;
    }
}



//another solution:



class Solution {
    public int missingNumber(int[] nums) {
        if(nums.length == 1 && nums[0] == 0){
            return 1;
        }
        if(nums.length == 1 && nums[0] == 1){
            return 0;
        }
        insertionSort(nums);
        for(int i = 0;i < nums.length;i++){
            if(nums[i] != i){
                return i;
            }
        }
        return nums.length; 
    }
    public void insertionSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i+1; j > 0 ; j--) {
                if(arr[j] < arr[j-1]){
                    swapArray(arr,j,j-1);
                }else {
                    break;
                }
            }
        }
    }
    public void swapArray(int[] arr,int first,int second){
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}