Kotlin Program to Find Missing Number in Array

You can find the missing number in an array of 1 to n by calculating the expected sum with n * (n + 1) / 2 and subtracting the actual sum of array elements; in Kotlin, use val missing = totalSum - arr.sum().

Examples

Input[1, 2, 4, 5, 6]

Output3

Input[1, 2, 3, 5]

Output4

Input[2, 3, 4, 5]

Output1

How to Think About It

To find the missing number, first understand that the numbers should be from 1 to n with one missing. Calculate the total sum of numbers from 1 to n using the formula n * (n + 1) / 2. Then find the sum of the given array. The difference between these two sums is the missing number.

Algorithm

1

Get the array of numbers and find its length n (which is one less than the full sequence length).

2

Calculate the total sum of numbers from 1 to n+1 using the formula <code>totalSum = (n+1) * (n+2) / 2</code>.

3

Calculate the sum of all elements in the array.

4

Subtract the array sum from the total sum to get the missing number.

5

Return or print the missing number.

Code

kotlin

fun findMissingNumber(arr: IntArray): Int {
    val n = arr.size + 1
    val totalSum = n * (n + 1) / 2
    val arrSum = arr.sum()
    return totalSum - arrSum
}

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

Output

Missing number is: 3

Dry Run

Let's trace the example array [1, 2, 4, 5, 6] through the code

1

Calculate n

Array size is 5, so n = 5 + 1 = 6

2

Calculate total sum

totalSum = 6 * (6 + 1) / 2 = 6 * 7 / 2 = 21

3

Calculate sum of array elements

arrSum = 1 + 2 + 4 + 5 + 6 = 18

4

Find missing number

missing = totalSum - arrSum = 21 - 18 = 3

Step	Value
n	6
totalSum	21
arrSum	18
missing	3

Why This Works

Step 1: Calculate total sum

The formula n * (n + 1) / 2 gives the sum of all numbers from 1 to n, which is the expected total if no number was missing.

Step 2: Sum of array elements

Adding all elements in the array gives the actual sum of the present numbers.

Step 3: Subtract to find missing

Subtracting the actual sum from the expected total reveals the missing number because it is the difference.

Alternative Approaches

Using XOR operation

kotlin

fun findMissingXOR(arr: IntArray): Int {
    val n = arr.size + 1
    var xorAll = 0
    for (i in 1..n) xorAll = xorAll xor i
    var xorArr = 0
    for (num in arr) xorArr = xorArr xor num
    return xorAll xor xorArr
}

fun main() {
    val arr = intArrayOf(1, 2, 4, 5, 6)
    println("Missing number is: ${findMissingXOR(arr)}")
}

XOR method uses bitwise operations and avoids overflow issues but is less intuitive for beginners.

Sorting and checking

kotlin

fun findMissingBySorting(arr: IntArray): Int {
    val sorted = arr.sorted()
    for (i in sorted.indices) {
        if (sorted[i] != i + 1) return i + 1
    }
    return sorted.size + 1
}

fun main() {
    val arr = intArrayOf(1, 2, 4, 5, 6)
    println("Missing number is: ${findMissingBySorting(arr)}")
}

Sorting method is simple but slower (O(n log n)) and uses extra space.

Complexity: O(n) time, O(1) space

Time Complexity

The program sums the array elements once, which takes O(n) time where n is the array length.

Space Complexity

Only a few variables are used for sums and calculations, so space complexity is O(1).

Which Approach is Fastest?

The sum formula approach is fastest and simplest; XOR is also O(n) but less intuitive; sorting is slower at O(n log n).

Approach	Time	Space	Best For
Sum formula	O(n)	O(1)	Fastest and simplest for missing number
XOR operation	O(n)	O(1)	Avoids overflow, uses bitwise logic
Sorting and checking	O(n log n)	O(n)	Simple but slower, uses extra space