Skip to content

Instantly share code, notes, and snippets.

@belarba

belarba/README.md

Created August 27, 2024 17:44
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save belarba/d7beeeb8f311f6eb7848d5fc00601d7a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save belarba/d7beeeb8f311f6eb7848d5fc00601d7a to your computer and use it in GitHub Desktop.
Download ZIP
Find nth Missing Number
Raw
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.
  1. 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.
Raw
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
Raw
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment