Discussion on: Write better code: Day 4 - Duplicate Space Edition

Used a version of binary search to do this..

Logic:

• Given that array is of range 1..n and of n+1 length. Atleast one is repeated - so number of unique integers is (n -1 + 1) = n
• E.g [3, 4, 6, 5, 4, 4, 2] -> length is 7 so range has to be 1..6 ; no of possible unique integers is (6-1 +1 = 6)
• The number of elements is always one greater than the number of unique possibilities.
• If we cut this in half - the condition should still hold true - so atleast one of those halves should have one more element that the number of unique possibilities.
• If the half you have chosen, does not have more elements than the number of unque possibilities, drop that half.
• If the half you have chosen, meets the condition, then cut it into two again.
• Repeat cutting in halves until you are left with just one item.

def space_edition(input_array)
  lowest_range = 1
  highest_range = input_array.length - 1

  while (lowest_range < highest_range)

    mid = (lowest_range + highest_range) /2

    first_half_lowest_range = lowest_range
    first_half_highest_range = mid

    second_half_lowest_range = mid + 1
    second_half_highest_range = highest_range

    number_of_elements_in_first_half = 0
    input_array.each do |number|
      if number >= first_half_lowest_range && number <= first_half_highest_range 
        number_of_elements_in_first_half += 1
      end

      number_of_unique_possibilities_in_first_half = first_half_highest_range - first_half_lowest_range + 1

      if number_of_elements_in_first_half > number_of_unique_possibilities_in_first_half
        lowest_range, highest_range = first_half_lowest_range, first_half_highest_range
      else
        lowest_range, highest_range = second_half_lowest_range, second_half_highest_range
      end
    end

  end

  return lowest_range
end

The problem asked for space efficiency, so we are doing this in-place without creating another array.
It has O[1] space, and O[logn] time as we used binary search (cutting in halves).

Note - there is a better way to improve this and reduce time to O[n]