DEV Community

loading...

Write better code: Day 4 - Duplicate Space Edition

arjunrajkumar profile image Arjun Rajkumar Updated on ・1 min read

This post originally appeared on Arjun Rajkumar's blog. Arjun is a web developer based in Bangalore, India.

--

Day 4: Question 1

Find a duplicate, Space Edition™.

We have an array of integers, where: The integers are in the range 1..n.
The array has a length of n+1.

It follows that our array has at least one integer which appears at least twice. But it may have several duplicates, and each duplicate may appear more than twice.

Write a method which finds an integer that appears more than once in our array. (If there are multiple duplicates, you only need to find one of them.)

We're going to run this method on our new, super-hip MacBook Pro With Retina Display™. Thing is, the damn thing came with the RAM soldered right to the motherboard, so we can't upgrade our RAM. So we need to optimize for space!

-

If you want to follow along, feel free to post your answers in the comment.

My answers are in the comments.
This problem is from InterviewCake.

Discussion (1)

pic
Editor guide
Collapse
arjunrajkumar profile image
Arjun Rajkumar Author

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]