Problem Solving

Problem Statement

You are given an array of size N-1 containing distinct integers from 1 to N. Exactly one number is missing from the array. Your task is to find that missing number.

Example:

        Input: arr = [1, 2, 4, 5, 6], N = 6
        Output: 3
        Explanation: 3 is missing in the array.
          

Example 2:

        Input: arr = [2,3,1,5], N = 5
        Output: 4
        Explanation: 4 is missing in the array.
          

Concept: Sum Formula (1 + 2 + … + N)

The sum of the first N natural numbers can be calculated using the formula:

        Sum = N * (N + 1) / 2
          

Why it works: The formula is derived from the idea of pairing numbers:

• Consider numbers 1, 2, 3, ..., N.
• Pair the first and last: 1 + N, 2 + (N-1), 3 + (N-2), ...
• There are N/2 pairs (if N is even), each summing to N+1.
• So the total sum = (N * (N + 1)) / 2

This sum represents the total of numbers if none were missing.

Solution Approach

1. Calculate the sum of first N natural numbers using the formula above.
2. Calculate the sum of all elements present in the given array.
3. The missing number is obtained by subtracting the array sum from the total sum.

Kotlin Solution

        fun findMissingNumber(arr: IntArray, n: Int): Int {
            val totalSum = n * (n + 1) / 2   // Step 1: Total sum of 1 to N
            val arraySum = arr.sum()          // Step 2: Sum of array elements
            return totalSum - arraySum        // Step 3: Subtract to get missing number
        }

        fun main() {
            val arr = intArrayOf(1, 2, 4, 5, 6)
            val n = 6
            val missing = findMissingNumber(arr, n)
            println("Missing number is: $missing") // Output: 3
        }
          

Step-by-Step Example

For arr = [1, 2, 4, 5, 6] and N = 6:

1. Total sum using formula: 6 * (6+1)/2 = 21
2. Sum of array elements: 1+2+4+5+6 = 18
3. Missing number: 21 - 18 = 3

Explanation of Why it Works

• The formula N*(N+1)/2 gives the sum of all numbers from 1 to N.
• The sum of the array gives the sum of present numbers only.
• The difference between the total sum and array sum isolates the missing number.

Complexity Analysis

• Time Complexity: O(N) — Calculating the sum of array elements.
• Space Complexity: O(1) — Only a few extra variables are used.

Edge Cases

• If the missing number is 1 or N, formula still works.
• If array is empty (N=1), it returns 1.
• For very large N, integer overflow can happen; use Long in Kotlin.