CODEWITHSUNDEEP
rubyarrays
user2945241
user2945241

Reputation: 360

Find lowest positive missing integer in array

I have array with integers something like this:

[1, 2, 3, 6, 10]

My question is what is the easiest way to get lowest positive integer that is not already in this array?

Something like:

[1, 2, 3, 6, 10].lowest_available => 4
[1, 8, 3, 6, 10].lowest_available => 2
[5, 8, 3, 6, 10].lowest_available => 1

Does any one have an idea how to manage this in ruby?

Upvotes: 2

Views: 2367

Answers (7)

Praful Patel
Praful Patel

Reputation: 105

To get the lowest possible number > 0 in an array containing negative values, I would add something to the given solution by @shivam, and finally, a function looks something like this:

def lowest_element(arr)
  res = nil
  arr = arr.reject { |e| e < 0 }
  arr.sort.each.with_index(1) do |e, i|
    if i != e
      res = i
      break
    end
  end
  res.nil? ? (arr.size > 0 ? arr.sort.last + 1 : 1) : res
end

lowest_element([1, 5, 6, 3, 8, 7, 2]) => 4
lowest_element([1, 5, 6, 3, 8, 7, 2, 4]) => 9
lowest_element([-1, -7, -9]) => 1
lowest_element([-1, -7, -9, 1]) => 2
lowest_element([-1, -7, -9, 0]) => 1

Upvotes: 1

user2960603
user2960603

Reputation: 1

There is a very simple way

def lowest_available (array)
  min = array.min
  max = array.max
  number = (min..max).to_a - array
  number = array.select { |v| v>0 }
  number = number.min + 1
end

What I am doing is to create another array that contains all numbers in the interval of the array in question. Once that is done, I remove the original array numbers from the created array Then I add 1 to the lowest number

Upvotes: 0

Cary Swoveland
Cary Swoveland

Reputation: 110675

Another way (it's late):

def first_missing(a)
  a.reduce(0) { |tot,n|
    exp=expected(tot); return exp if n>exp; tot + n }
end

def expected(tot)
  ((-1.0 + Math.sqrt(1.0+8*tot))/2).round + 1
end

first_missing([1, 2, 3, 6, 10]) #=> 4
first_missing([1, 8, 3, 6, 10]) #=> 2
first_missing([5, 8, 3, 6, 10]) #=> 1

Upvotes: 0

shivam
shivam

Reputation: 16506

By lowest i mean integer that is > 0 and not already in the array

Basically you are looking for the first value that is not equal to its index+1 when sorted. Here:

def lowest_available(arr)
  res = nil
  arr.sort.each.with_index(1) { |a, i|
    if i != a
      res = i
      break
    end
  }
  res
end

lowest_available([1, 2, 3, 6, 10])
# => 4

lowest_available([1, 8, 3, 6, 10])
# => 2

lowest_available([5, 8, 3, 6, 10])
# => 1

Update

The above method can be shortened by returning value along with break. (As suggested by Cary and Stefan in comments below).

def lowest_available(arr)
  arr.sort.find.with_index(1) { |a, i| break i if i != a }
end

Upvotes: 2

sawa
sawa

Reputation: 168091

class Array
  def lowest_available; (1..Float::INFINITY).find{|e| include?(e).!} end
end

[1, 2, 3, 6, 10].lowest_available # => 4
[1, 8, 3, 6, 10].lowest_available # => 2
[5, 8, 3, 6, 10].lowest_available # => 1

or, as suggested by Stefan:

class Array
  def lowest_available; 1.step.find{|e| include?(e).!} end
end

Upvotes: 4

Stefan
Stefan

Reputation: 114158

Not that elegant, but if your arrays are small, you could create the entire integer array and use Array#- to find the difference:

def lowest_available(arr)
  ((1..arr.size).to_a - arr).first
end

lowest_available([1, 2, 3, 6, 10]) #=> 4
lowest_available([1, 8, 3, 6, 10]) #=> 2
lowest_available([5, 8, 3, 6, 10]) #=> 1

Upvotes: 2

Robert Norden
Robert Norden

Reputation: 100

  1. Sort the array
  2. Iterate over the array and compare each item's value with the current index+1, if this pair is not equal you found the lowest available integer which is index+1.

Upvotes: 0

Related Questions