Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Array

Missing Number

Array, Iterative Approach

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.

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.

Constraints:

  • n == nums.length

  • 1 <= n <= 104

  • 0 <= nums[i] <= n

  • All the numbers of nums are unique.

Solutions

Approach - Brute Force Technique

This solution is considered a brute force approach because it checks each candidate number against all numbers in the array.

Steps

  1. Outer Loop: The outer loop iterates over all numbers from 0 to nums.Length. Each number in this range is a potential candidate for the missing number.

  2. Inner Loop and Flag Initialization: For each candidate number, a boolean flag found is initialized to false, and an inner loop iterates over all numbers in the array nums.

  3. Number Checking: Inside the inner loop, it checks if the current number in the array nums is equal to the candidate number. If it is, it sets found to true and breaks the inner loop.

  4. Missing Number Identification: After the inner loop, it checks the flag found. If found is still false, it means the candidate number was not found in the array nums, so it returns the candidate number as the missing number.

  5. Completion: The function continues this process until it finds a missing number or it has checked all candidate numbers. If it has checked all candidate numbers and hasn’t found a missing number, it returns -1. However, according to the problem statement, there should always be one missing number, so this line should never be reached.

public class Solution {
    public int MissingNumber(int[] nums) {
        for (int i = 0; i <= nums.Length; i++) {
            bool found = false;
            for (int j = 0; j < nums.Length; j++) {
                if (nums[j] == i) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                return i;
            }
        }
        return -1; // This line should never be reached.
    }
}

Complexity

  • Time Complexity: O(N^2)

  • Auxiliary Space: O(1)

Approach - Iterative Technique

Steps

  1. Expected Sum Calculation: The function calculates the expected sum of all numbers from 0 to nums.Length using the formula for the sum of an arithmetic series: nums.Length*(nums.Length+1)/2. This sum is stored in expectedSum.

  2. Actual Sum Calculation: The function then calculates the actual sum of all numbers in the array nums by iterating over each number in nums and adding it to actualSum.

  3. Missing Number Calculation: Finally, the function calculates the missing number by subtracting actualSum from expectedSum. The result is the number that is missing from the array nums.

public class Solution {
    public int MissingNumber(int[] nums) {
        
        int expectedSum=nums.Length*(nums.Length+1)/2;
        int actualSum=0;
        foreach(var num in nums)actualSum+=num;
        return expectedSum-actualSum;
        
    }
}

Complexity

  • Time Complexity: O(N)

  • Auxiliary Space: O(1)

PreviousContainer With Most WaterNextRoman to Integer

Last updated 1 year ago