Ruby Program to Find Missing Number in Array

You can find the missing number in an array of consecutive numbers by calculating the expected sum with n * (n + 1) / 2 and subtracting the actual sum of the array, like missing = (n * (n + 1) / 2) - array.sum.

Examples

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

Output3

Input[2, 3, 4, 6, 7, 8]

Output5

Input[1, 3]

Output2

How to Think About It

To find the missing number, first understand that the numbers should form a complete sequence from 1 to n. Calculate the sum of all numbers from 1 to n using the formula n * (n + 1) / 2. Then subtract the sum of the given numbers from this total. The difference is the missing number.

Algorithm

1

Get the input array of numbers.

2

Find the maximum number n in the array (assuming numbers start from 1).

3

Calculate the expected sum of numbers from 1 to n using the formula n*(n+1)/2.

4

Calculate the actual sum of the numbers in the array.

5

Subtract the actual sum from the expected sum to find the missing number.

6

Return the missing number.

Code

ruby

def find_missing_number(arr)
  n = arr.max
  expected_sum = n * (n + 1) / 2
  actual_sum = arr.sum
  missing = expected_sum - actual_sum
  missing
end

# Example usage
array = [1, 2, 4, 5, 6]
puts find_missing_number(array)

Output

3

Dry Run

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

1

Find maximum number

Maximum number n = 6

2

Calculate expected sum

expected_sum = 6 * (6 + 1) / 2 = 21

3

Calculate actual sum

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

4

Find missing number

missing = 21 - 18 = 3

Step	Value
n	6
expected_sum	21
actual_sum	18
missing	3

Why This Works

Step 1: Calculate expected sum

The formula n * (n + 1) / 2 gives the sum of all numbers from 1 to n without missing any.

Step 2: Sum actual array values

Adding all numbers in the array gives the total of present numbers.

Step 3: Subtract to find missing

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

Alternative Approaches

Using XOR operation

ruby

def find_missing_xor(arr)
  n = arr.max
  xor_all = (1..n).reduce(:^)
  xor_arr = arr.reduce(:^)
  xor_all ^ xor_arr
end

array = [1, 2, 4, 5, 6]
puts find_missing_xor(array)

XOR method uses bitwise operations and can be faster for large arrays but is less intuitive.

Using sorting and checking neighbors

ruby

def find_missing_sort(arr)
  arr.sort.each_cons(2) do |a, b|
    return a + 1 if b != a + 1
  end
  nil
end

array = [1, 2, 4, 5, 6]
puts find_missing_sort(array)

Sorting method is easy to understand but slower due to sorting overhead.

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

Time Complexity

Calculating the sum of the array takes O(n) time where n is the number of elements. The rest are constant time operations.

Space Complexity

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

Which Approach is Fastest?

The sum formula method is fastest and simplest. XOR is also O(n) but less readable. Sorting is slower at O(n log n).

Approach	Time	Space	Best For
Sum formula	O(n)	O(1)	Simple and fast for 1 to n sequences
XOR operation	O(n)	O(1)	Bitwise approach, efficient but less intuitive
Sorting and checking	O(n log n)	O(1)	Easy to understand, slower for large arrays