Arrays Masterclass: Missing Number, Max Consecutive Ones, and Single Number (Arrays Part-3)

This lecture focuses on three core array manipulation problems frequently asked in technical coding interviews: Finding the Missing Number in an Array (1 to $N$ ), Maximum Consecutive 1s, and Finding the Element That Appears Once (Single Number). Beyond solving these specific problems, the module demonstrates how to drive technical interviews by evolving code logically from Brute Force $\rightarrow$ Better (Hashing) $\rightarrow$ Optimal (Mathematical / Bit Manipulation) approaches.

1. Driving the Interview: The Brute-to-Optimal Mindset

When solving Data Structures and Algorithms (DSA) problems during technical interviews, jumping directly to the optimal solution can hurt your evaluation. Interviewers evaluate your thought process, edge-case awareness, and system optimization skills.

Structure & Concept Flow

Candidate Thought Workflow

+--> 1. State Brute Force Approach (Establishes baseline & logic)

+--> 2. Identify Bottlenecks (Time complexity / Space overhead)

+--> 3. Propose Better Solution (Frequency Arrays / Hash Maps)

+--> 4. Derive Optimal Solution (Math Tricks / Bit Manipulation)

+--> 5. Analyze Edge Cases & Machine Limitations (Integer Overflow)

Interview Rubric Note: Showing why an optimal solution is chosen (e.g., explaining why XOR outperforms Summation due to integer overflow prevention) separates high-performing candidates from those who simply memorize code.

2. Problem 1 — Find Missing Number: Problem Statement & Brute Force Approach

Problem Statement

Given an integer $N$ and an array containing $N-1$ distinct numbers selected from the range $[1, N]$ , find the single number that is missing from the array.

Example:
$N = 5$ , $\text{Array} = [1, 2, 4, 5]$
Output: $3$ (since numbers from $1$ to $5$ are expected, and $3$ is absent).

Brute Force Approach: Nested Linear Search

Check every integer $i$ from $1$ to $N$ to see if it exists in the array using a linear search for each number.

Algorithm Steps

Outer loop runs from $i = 1$ to $N$ .
Inner loop iterates over the array $[0 \dots N-2]$ to search for $i$ .
If $i$ is found, set a flag = 1 and break out of the inner loop.
If after checking the entire array flag remains 0, then $i$ is the missing number.

C++

int missingNumberBrute(vector<int>& a, int N) {
    for (int i = 1; i <= N; i++) {
        int flag = 0;
        for (int j = 0; j < N - 1; j++) {
            if (a[j] == i) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) return i;
    }
    return -1;
}

Complexity Analysis

Time Complexity: $O(N^2)$
In the worst case (e.g., $N$ is missing at the end), the outer loop runs $N$ times and the inner loop runs up to $N-1$ times.
Space Complexity: $O(1)$
No additional dynamic memory allocated.

3. Problem 1 — Better Approach via Hashing

To avoid the quadratic runtime of nested searching, trade space for time by caching frequency counts in a Hash Array.

Hashing Strategy

Create an array of size $N + 1$ (initialized to 0). Iterate through the input array and set hash[a[i]] = 1. Then, scan the hash array from index $1$ to $N$ ; the index containing 0 is the missing element.

C++

int missingNumberBetter(vector<int>& a, int N) {
    vector<int> hash(N + 1, 0);
    
    // Step 1: Store frequencies
    for (int i = 0; i < N - 1; i++) {
        hash[a[i]] = 1;
    }
    
    // Step 2: Find the zero frequency index
    for (int i = 1; i <= N; i++) {
        if (hash[i] == 0) {
            return i;
        }
    }
    return -1;
}

CODE

Input Array: [1, 2, 4, 5], N = 5

Hash Array Initialization (Size 6):
Index:  [0]  [1]  [2]  [3]  [4]  [5]
Val:     0    0    0    0    0    0

After Frequency Pass:
Index:  [0]  [1]  [2]  [3]  [4]  [5]
Val:     0    1    1    0    1    1
                        ^
                  Missing element = 3

Complexity Analysis

Time Complexity: $O(2N) = O(N)$
One pass of size $N-1$ to populate hash + one pass of size $N$ to inspect.
Space Complexity: $O(N)$
Requires extra array of size $N+1$ .

4. Problem 1 — Optimal Solution 1: Summation Formula & Integer Overflow Risk

We can eliminate the $O(N)$ space overhead using the mathematical sum of the first $N$ natural numbers:

\text{Sum}_N = \frac{N \times (N + 1)}{2}

Subtracting the actual sum of elements in the array ( $S_2$ ) from $\text{Sum}_N$ yields the missing number.

\text{Missing Number} = \text{Sum}_N - S_2

C++

int missingNumberSum(vector<int>& a, int N) {
    // Calculate theoretical sum
    long long sumN = ((long long)N * (N + 1)) / 2;
    
    // Calculate actual array sum
    long long S2 = 0;
    for (int i = 0; i < N - 1; i++) {
        S2 += a[i];
    }
    
    return sumN - S2;
}

Warning: Production & Interview Pitfall (Integer Overflow)
If $N = 10^5$ , $N \times (N + 1) \approx 10^{10}$ , which exceeds the standard 32-bit signed integer maximum limit ( $2^{31} - 1 \approx 2.14 \times 10^9$ ). You must cast the sum to a 64-bit data type (long long in C++, long in Java) to prevent overflow bugs.

5. Problem 1 — Optimal Solution 2: XOR Bit Manipulation (The Supreme Approach)

To optimize space without risking integer overflow, use the bitwise XOR ( $\oplus$ ) operator.

Fundamental XOR Properties

Self-Cancellation: $X \oplus X = 0$ (XORing identical numbers yields zero).
Identity: $X \oplus 0 = X$ (XORing any number with zero returns the original number).
Commutativity & Associativity: Order of operations does not alter the result.

Mental Model & Mechanics

If you compute the XOR of all numbers from $1 \dots N$ ( $\text{XOR}_1$ ) and XOR it with all elements present in the array ( $\text{XOR}_2$ ), every number present in both sets cancels itself out, leaving only the missing number.

\text{Result} = (1 \oplus 2 \oplus 3 \dots \oplus N) \oplus (\text{arr}[0] \oplus \text{arr}[1] \dots \oplus \text{arr}[N-2])

Structure & Concept Flow

Given Array = [1, 2, 4, 5], N = 5

XOR1 (1 to N) : 1 ^ 2 ^ 3 ^ 4 ^ 5

XOR2 (Array) : 1 ^ 2 ^ 4 ^ 5

-----------------------------------

Combined XOR : (1^1) ^ (2^2) ^ 3 ^ (4^4) ^ (5^5)

= 0 ^ 0 ^ 3 ^ 0 ^ 0

= 3

Loop Unification Optimization (Single-Pass Execution)

Instead of running two separate loops to calculate $\text{XOR}_1$ and $\text{XOR}_2$ , combine them inside a single loop:

C++

int missingNumberXOR(vector<int>& a, int N) {
    int xor1 = 0;
    int xor2 = 0;
    
    for (int i = 0; i < N - 1; i++) {
        xor2 = xor2 ^ a[i];     // Array element XOR
        xor1 = xor1 ^ (i + 1);  // Range [1 to N-1] XOR
    }
    
    xor1 = xor1 ^ N;            // Incorporate N into the range XOR
    
    return xor1 ^ xor2;         // Missing number isolated
}

6. Problem 1 — Code Implementation & Performance Synthesis

Summation vs. XOR: Which is Better?

Metric	Summation Approach	Bitwise XOR Approach
Time Complexity	$O(N)$	$O(N)$
Space Complexity	$O(1)$	$O(1)$
Max Bit Requirement	Can exceed 32 bits ( $10^{10}$ requires 64-bit int)	Never exceeds $N$ (Fits safely in standard 32-bit int)
Performance	Slightly faster arithmetic operations	Highly optimized at hardware bit-level

7. Problem 2 — Max Consecutive Ones: Problem Analysis & Single-Pass State Tracking

Problem Statement

Given a binary array consisting of only 0s and 1s, return the maximum number of consecutive 1s present in the array.

Example:
$\text{Input} = [1, 1, 0, 1, 1, 1, 0, 1, 1]$
Output: $3$

Algorithm & State Tracking

Maintain two scalar counter variables during a single iteration:

cnt: Tracks current contiguous sequence of 1s.
maxi: Stores global peak count achieved so far.

CODE

Array Iteration Trace:
Index:   0    1    2    3    4    5    6    7    8
Val:    [1,   1,   0,   1,   1,   1,   0,   1,   1]
cnt:     1    2    0    1    2    3    0    1    2
maxi:    1    2    2    2    2    3    3    3    3
                   ^               ^
              Reset cnt       Max updated

Complete Code (C++)

C++

int findMaxConsecutiveOnes(vector<int>& nums) {
    int maxi = 0;
    int cnt = 0;
    
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == 1) {
            cnt++;
            maxi = max(maxi, cnt);
        } else {
            cnt = 0; // Reset counter on encountering 0
        }
    }
    
    return maxi;
}

Complexity Analysis

Time Complexity: $O(N)$ (Single traversal).
Space Complexity: $O(1)$ (Only two local variables used).

8. Problem 3 — Find the Element That Appears Once: Problem Statement & Brute Force

Problem Statement

Given a non-empty array of integers where every element appears twice except for one, find that single unique element.

Example:
$\text{Input} = [4, 1, 2, 1, 2]$
Output: $4$

Brute Force Approach: Linear Frequency Counting

For each element in the array, run an inner loop over the entire array to count its total occurrences.

C++

int getSingleElementBrute(vector<int>& arr) {
    int n = arr.size();
    
    for (int i = 0; i < n; i++) {
        int num = arr[i];
        int count = 0;
        
        for (int j = 0; j < n; j++) {
            if (arr[j] == num) {
                count++;
            }
        }
        
        if (count == 1) return num;
    }
    
    return -1;
}

Complexity Analysis

Time Complexity: $O(N^2)$
Space Complexity: $O(1)$

9. Problem 3 — Better Approach: Array Hashing vs. Hash Maps (Trade-offs & Edge Cases)

Alternative 1: Direct Array Hashing

Determine the maximum element ( $\text{MaxC}$ ), instantiate a hash array of size $\text{MaxC} + 1$ , and populate occurrences.

C++

int getSingleElementHashArray(vector<int>& arr) {
    int n = arr.size();
    int maxi = arr[0];
    for (int i = 0; i < n; i++) maxi = max(maxi, arr[i]);
    
    vector<int> hash(maxi + 1, 0);
    for (int i = 0; i < n; i++) hash[arr[i]]++;
    
    for (int i = 0; i < n; i++) {
        if (hash[arr[i]] == 1) return arr[i];
    }
    
    return -1;
}

Limitations of Array Hashing:

Negative Integers: Array indices cannot be negative (e.g., arr[i] = -5 breaks index access).

Memory Explosion: If maximum element is $10^9$ , declaring an array of size $10^9 + 1$ causes a Memory Limit Exceeded (MLE) crash.

Alternative 2: Hash Map (`std::map` / `unordered_map`)

To handle negative numbers and large integer values efficiently, map keys to their frequency counts.

C++

int getSingleElementMap(vector<int>& arr) {
    int n = arr.size();
    
    // Key: Element, Value: Frequency
    unordered_map<int, int> mpp;
    for (int i = 0; i < n; i++) {
        mpp[arr[i]]++;
    }
    
    // Find key with frequency 1
    for (auto it : mpp) {
        if (it.second == 1) {
            return it.first;
        }
    }
    
    return -1;
}

Hash Map Complexity Breakdown

Data Structure Used	Time Complexity (Insertion & Search)	Space Complexity
`std::map` (Ordered Red-Black Tree)	$O(N \log M)$ where $M = \frac{N}{2} + 1$	$O(M)$
`std::unordered_map` (Best/Average Case)	$O(N)$ total time	$O(M)$
`std::unordered_map` (Worst Case - Collision Attack)	$O(N^2)$ total time	$O(M)$

Note: $M = \frac{N}{2} + 1$ because almost all elements appear twice, making map size roughly half of $N$ .

10. Problem 3 — Optimal Solution: XOR Self-Cancellation Property

By using bitwise XOR, we achieve $O(N)$ runtime with $O(1)$ space, bypassing hash collision risks entirely.

Conceptual Workflow

Since XOR is associative and commutative:

\text{arr}[0] \oplus \text{arr}[1] \dots \oplus \text{arr}[N-1]

All paired elements cancel each other out ( $x \oplus x = 0$ ), leaving only the unique element ( $0 \oplus \text{unique} = \text{unique}$ ).

CODE

Input: [4, 1, 2, 1, 2]

Bitwise Operation Sequence:
  4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4

Complete Code (C++)

C++

int getSingleElementOptimal(vector<int>& arr) {
    int xorr = 0;
    for (int i = 0; i < arr.size(); i++) {
        xorr = xorr ^ arr[i];
    }
    return xorr;
}

Complexity Analysis

Time Complexity: $O(N)$ (Single linear sweep).
Space Complexity: $O(1)$ (Single register state).

11. Comparative Analysis & Algorithm Selection Matrix

Here is an overview comparing the approaches across all three problems discussed in this masterclass:

Problem	Approach Strategy	Time Complexity	Space Complexity	Primary Trade-Off / Edge Case
Missing Number	Brute (Nested Loops)	$O(N^2)$	$O(1)$	Impractical runtime for large inputs ( $N > 10^4$ ).
	Frequency Array	$O(N)$	$O(N)$	High memory usage due to auxiliary array setup.
	Summation Formula	$O(N)$	$O(1)$	Integer Overflow Risk ( $N \times (N+1)$ exceeds 32 bits).
	Bitwise XOR	$O(N)$	$O(1)$	Optimal. No overflow risks, single-pass optimized loop.
Max Consecutive Ones	Single Pass Pointer	$O(N)$	$O(1)$	Optimal. Requires immediate state reset upon `0`.
Single Number	Brute (Nested Search)	$O(N^2)$	$O(1)$	Extremely inefficient for large input arrays.
	Array Hashing	$O(N)$	$O(\text{MaxElement})$	Fails on negative numbers and large integers ( $10^9$ ).
	Hash Map	$O(N)$ avg / $O(N^2)$ worst	$O(\frac{N}{2})$	Worst-case time complexity degrades during hash collisions.
	Bitwise XOR	$O(N)$	$O(1)$	Optimal. Universal array support, minimal memory overhead.

12. Summary and Key Takeaways

Structured Interview Delivery: Always lead with the Brute Force approach to establish problem comprehension, highlight its algorithmic bottlenecks, and then systematically progress to optimal solutions.
Summation vs. XOR for Missing Numbers: While Summation yields $O(N)$ time and $O(1)$ space, XOR is superior because it avoids 64-bit integer overflow issues when $N$ is large ( $N \ge 10^5$ ).
Single-Pass XOR Unification: In the Missing Number problem, combining the range XOR ( $1 \dots N$ ) and the array element XOR inside a single loop eliminates redundant traversal passes.
Consecutive Counting Pattern: Track contiguous binary states by incrementing a local counter on target hits (1) and instantly resetting it to zero when interrupted by non-target elements (0).
Array Hashing Constraints: Frequency arrays are limited by non-negative domain inputs and bounded integer ranges.
XOR Self-Cancellation: Use the bitwise property ( $x \oplus x = 0$ ) to isolate single unique elements from paired duplicates in $O(N)$ time and $O(1)$ space.

Find element that appears once | Find missing number | Max Consecutive number of 1's | Arrays Part-3

Arrays Masterclass: Missing Number, Max Consecutive Ones, and Single Number (Arrays Part-3)

1. Driving the Interview: The Brute-to-Optimal Mindset

2. Problem 1 — Find Missing Number: Problem Statement & Brute Force Approach

Problem Statement

Brute Force Approach: Nested Linear Search

Algorithm Steps

Complexity Analysis

3. Problem 1 — Better Approach via Hashing

Hashing Strategy

Complexity Analysis

4. Problem 1 — Optimal Solution 1: Summation Formula & Integer Overflow Risk

5. Problem 1 — Optimal Solution 2: XOR Bit Manipulation (The Supreme Approach)

Fundamental XOR Properties

Mental Model & Mechanics

Loop Unification Optimization (Single-Pass Execution)

6. Problem 1 — Code Implementation & Performance Synthesis

Summation vs. XOR: Which is Better?

7. Problem 2 — Max Consecutive Ones: Problem Analysis & Single-Pass State Tracking

Problem Statement

Algorithm & State Tracking

Complete Code (C++)

Complexity Analysis

8. Problem 3 — Find the Element That Appears Once: Problem Statement & Brute Force

Problem Statement

Brute Force Approach: Linear Frequency Counting

Complexity Analysis

9. Problem 3 — Better Approach: Array Hashing vs. Hash Maps (Trade-offs & Edge Cases)

Alternative 1: Direct Array Hashing

Alternative 2: Hash Map (std::map / unordered_map)

Hash Map Complexity Breakdown

10. Problem 3 — Optimal Solution: XOR Self-Cancellation Property

Conceptual Workflow

Complete Code (C++)

Complexity Analysis

11. Comparative Analysis & Algorithm Selection Matrix

12. Summary and Key Takeaways

Alternative 2: Hash Map (`std::map` / `unordered_map`)