Missing Number (LeetCode)

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.
Solutions(Java):
1. class Solution {
   public int missingNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            int correct = nums[i];
            if (nums[i] < nums.length &&nums[i] != nums[correct])
                swap(nums, i, correct);
            else 
                i++;
        }
        for (int j = 0; j <nums.length; j++){
            if ( nums[j] != j)
                return j;
        }
        return nums.length;
    }
    void swap(int[] nums, int i, int correct) {
        int temp = nums[i];
        nums[i] = nums[correct];
        nums[correct] = temp;
    }
}
2. class Solution {
public int missingNumber(int[] nums) { int sum = 0; int idealSum = 0; int i = 0; for(i = 0; i < nums.length; i++) { sum = sum + nums[i]; idealSum = idealSum + i; } idealSum = idealSum + i; return idealSum - sum; } }


Comments

Post a Comment

Popular posts from this blog

Final Value of Variable After Performing Operations (LeetCode)

  There is a programming language with only   four   operations and   one   variable   X : ++X  and  X++   increments  the value of the variable  X  by  1 . --X  and  X--   decrements  the value of the variable  X  by  1 . Initially, the value of  X  is  0 . Given an array of strings  operations  containing a list of operations, return  the  final  value of  X   after performing all the operations .   Example 1: Input: operations = ["--X","X++","X++"] Output: 1 Explanation:  The operations are performed as follows: Initially, X = 0. --X: X is decremented by 1, X = 0 - 1 = -1. X++: X is incremented by 1, X = -1 + 1 = 0. X++: X is incremented by 1, X = 0 + 1 = 1. Solutions: class Solution { public int finalValueAfterOperations(String[] operations) { int val=0; for(int i=0; i<operations.length; i++){ if(operations[i].charAt(1)=='+') val++; else val--; } return val
Read more

Java Output Formatting | Hackerrank

  Java's   System.out.printf   function can be used to print formatted output. The purpose of this exercise is to test your understanding of formatting output using   printf . To get you started, a portion of the solution is provided for you in the editor; you must format and print the input to complete the solution. Input Format Every line of input will contain a  String  followed by an  integer . Each  String  will have a maximum of   alphabetic characters, and each  integer  will be in the inclusive range from   to  . Output Format In each line of output there should be two columns: The first column contains the  String  and is left justified using exactly   characters. The second column contains the  integer , expressed in exactly   digits; if the original input has less than three digits, you must pad your output's leading digits with zeroes. Sample Input java 100 cpp 65 python 50 Sample Output ================================ java 100 cpp 065 python
Read more

China will fight six wars in the next 50 years!

 (The source of this content:  Tap Here  ) China is a big country without unity. This is the shame of the Chinese nation and the shame of the descendants of Yan and Huang.  For the unity of the country and the dignity of the nation, China must wage six wars in the next 50 years. It may be a nationwide war or a local war. But no matter which war, China must wage a united war.   　　 The first war: reunification of Taiwan (2020-2025)   　　Although the two sides of the strait are becoming more and more peaceful, don't assume that the Taiwan's ruling authority (whether it is the KMT or the DPP) will peacefully reunify with the mainland. This is not in line with the ruling authority's campaign needs, so it will maintain the status quo with the mainland for a long time. The party is in favor, the DPP makes trouble, the Kuomintang and Yihe each obtain more political bargaining chips from it, "independence" dare not really "independence", make trouble, "unific
Read more