Lecture Notes on Finding Missing Number and Other Problems

Course Overview

• Lecture from Stryber's A2Z DSA course.
• Covers 455 modules and 400+ problems.
• Aims to prepare for DS Algorithms in interviews worldwide.

Problem 1: Finding Missing Number in an Array

Problem Statement

• Given n and n-1 numbers in an array containing numbers between 1 to n.
• Identify the missing number.
  • Example: For n = 5, if array = [1, 2, 4, 5], missing number is 3.

Solution Approaches

1. Brute Force Solution

• Iterate through each number from 1 to n and check if it exists in the array.
• Implementation steps:
  1. Use a loop from 1 to n.
  2. For each number, perform a linear search in the array.
  3. If the number is not found, it is the missing number.
• Time Complexity: O(n^2) in the worst case.
• Space Complexity: O(1).

2. Hashing Solution (Better Solution)

• Use a hash array of size n+1 initialized to 0.
• Mark the presence of numbers by incrementing their corresponding index in the hash array.
• Check the hash array to find the index that is still 0.
• Time Complexity: O(n).
• Space Complexity: O(n).

3. Optimal Solutions

• Method 1: Sum Formula

  • Use the formula for the sum of the first n natural numbers: n(n + 1) / 2.
  • Calculate the difference between this sum and the sum of the array.
  • Time Complexity: O(n).
  • Space Complexity: O(1).

• Method 2: ZOR

  • Use the property that x ⊕ x = 0 for any integer x.
  • XOR all numbers from 1 to n and all elements in the array. The result will be the missing number.
  • Time Complexity: O(n).
  • Space Complexity: O(1).

Problem 2: Maximum Consecutive Ones

Problem Statement

• Given an array of 0s and 1s, find the length of the longest subarray of 1s.

Optimal Solution

• Initialize counters to track the number of consecutive 1s and the maximum count.
• Iterate through the array:
  • If the current element is 1, increment the counter.
  • If it's 0, reset the counter.
  • Update the maximum count whenever the counter exceeds it.
• Time Complexity: O(n).
• Space Complexity: O(1).

Problem 3: Finding Number Appearing Once

Problem Statement

• In an array where every number appears twice except one, find the number that appears once.

Solution Approaches

1. Brute Force Solution

• Use nested loops to count occurrences of each number in the array.
• Time Complexity: O(n^2).
• Space Complexity: O(1).

2. Hashing (Better Solution)

• Use a hash map to track occurrences of each number.
• After populating the hash map, iterate over it to find the number that appears once.
• Time Complexity: O(n).
• Space Complexity: O(n).

3. Optimal Solution using ZOR

• Use the ZOR method to cancel out the numbers appearing twice.
• Implement as follows:
  • Initialize ZOR to 0.
  • XOR all elements of the array.
  • The result will be the number that appears once.
• Time Complexity: O(n).
• Space Complexity: O(1).

Key Takeaways

• Approach problems from brute force to better and then to optimal solutions.
• Use hashing or mathematical properties (like sum or ZOR) for efficiency in finding missing elements or unique numbers.
• Understand the implications of time and space complexity in choosing the right solution.