Find nth Missing Number

README.md

Find Missing Number

Description

This function, find_missing_number, takes an unsorted array of unique integers that form a sequence and returns the nth missing number in that sequence, defaulting to the first missing number if nth is not specified. The smallest number in the sequence is assumed to be 1, and all numbers are positive.

Examples

1. Example 1:

   arr = [4, 3, 6, 2, 1, 7]
   puts find_missing_number(arr) # Output: 5

2. Example 2:

   arr = [4, 3, 6, 2, 1, 7, 9]
   puts find_missing_number(arr, nth: 2) # Output: 8

3. Example 3:

   arr = [4, 3, 6, 2, 1, 7, 9]
   puts find_missing_number(arr, nth: 3) # Output: 10

Requirements

Ruby: Ensure you have Ruby installed (version 2.5+).

RSpec: Used for running tests. Install it if you don't have it by running: gem install rspec

How to Run

1. Running the Function:

• You can directly call the function in your Ruby code or use the examples provided.

2. Running the Tests:

• The tests are written using RSpec. To run the tests, execute the following command in your terminal:

  rspec find_missing_number_spec.rb

File Structure

• find_missing_number.rb Contains the find_missing_number function
• find_missing_number_spec.rb Contains the RSpec tests for the function
• README.md This file with instructions on how to use the solution

Notes

• The function works efficiently for typical sequences and handles edge cases such as an empty array or when the nth missing number is negative or outside the given sequence range.

find_missing_number.rb

def find_missing_number(arr, nth: 1)
  return "We only check position 1 or higher" if nth < 1
  return nth if arr.empty?

  # ordenate the received array
  arr.sort!
  missing_numbers = []
  
  # The smallest number in a sequence is 1
  internal_counter = 1
  index = 0
  
  # Will run until we have the nth missing number
  while missing_numbers.length < nth
    # Use a index to move throught the received array and
    # compare the received array with a "internal counter"
    if index < arr.length && arr[index] == internal_counter
      index += 1
    else
      missing_numbers << internal_counter
    end
    internal_counter += 1
  end
  
  # as the start index is 0
  missing_numbers[nth - 1]
end

find_missing_number_spec.rb

require 'rspec'

RSpec.describe 'find_missing_number' do
  it 'finds the 1st missing number in a simple sequence' do
    arr = [4, 3, 6, 2, 1, 7]
    expect(find_missing_number(arr)).to eq(5)
  end

  it 'finds the 2nd missing number in a sequence' do
    arr = [4, 3, 6, 2, 1, 7, 9]
    expect(find_missing_number(arr, nth: 2)).to eq(8)
  end

  it 'finds the 3rd missing number in a sequence' do
    arr = [4, 3, 6, 2, 1, 7, 9]
    expect(find_missing_number(arr, nth: 3)).to eq(10)
  end

  it 'handles an empty array' do
    arr = []
    expect(find_missing_number(arr)).to eq(1)
  end

  it 'handles when nth missing number is outside the array range' do
    arr = [1, 2, 3, 4, 5]
    expect(find_missing_number(arr, nth: 2)).to eq(7)
  end
  
  it 'handles when nth is negative' do
    arr = [1, 2, 3, 4, 5]
    expect(find_missing_number(arr, nth: -2)).to eq("We only check position 1 or higher")
  end
end