Heavy Pill

Cracking the Coding Interview is a book that many swear by, but can also instill fear and anxiety in interviewees. It has been referred to as the interviewing bible for programmers so I've been working through some of its lessons and practice problems. The book is comprised of both very challenging problems/concepts and problems/concepts that may seem tricky but are actually quite simple.

I'm going to go over one of the problems that seems difficult at first, but is easy to conceptualize with the right strategy. The problem is called 'The Heavy Pill'. It describes a scenario where there are multiple bottles of pills and all but one contain pills that weight 1 gram each; the other bottle contains pills that weigh 1.1 grams each. The problem asks to find the heavy bottle with a scale that can only be used once.

My initial instinct was to write a function that required multiple trips to the scale. It would check the weight of one pill from each bottle until it found a pill that weighed 1.1 grams, then it'd return that bottle number. This would not satisfy the criteria defined in the problem but would look something like this:

function cheatHeavy(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 1.1) return `The heavy pill is in bottle number ${i + 1}.`;
  }
}

cheatHeavy([1, 1.1, 1, 1, 1, 1, 1]); // => 'The heavy pill is in bottle number 2.'

The correct solution is actually not much more complex:

function findHeavy(arr) {
  let pillBag = 0;
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    pillBag += (arr[i] * (i + 1));
    count += i + 1;
  }
  return `The heavy pill is in bottle number ${(pillBag - count) * 10}.`;
}

findHeavy([1, 1, 1, 1, 1.1, 1, 1]); // => 'The heavy pill is in bottle number 5.'

This solution utilizes a simple strategy to allow for only one trip to the scale. The idea behind this solution is that if you collect a different number of pills from each bottle, and record how many were taken from each, the difference between the total number of pills and the weight at the end will indicate which bottle had the heaviest pills.

The function I wrote begins with a couple tracking variables (in real-world application 'pillBag' represents a bag that collects the pills that are being pulled from each bottle, and 'count' represents the total number of pills in the bag). The for-loop simply adds pills to 'pillBag', and tracks how many pills have been taken in 'count'. In my return statement, when I subtract 'count' from 'pillBag' I am left with a number divisible by 0.1; the quotient represent the numbers of 1.1-grams-pills that were added to pillBag - this number allows us to identify which bottle had the heavy pills. (For simplicity's sake I multiplied the weight/count difference by 10 instead of dividing by 0.1)

Working through this problem gave me an appreciation for how a seemingly complex problem often calls for a simple solution :)

Sources:

1. Cracking the Coding Interview, by Gayle Laakmann McDowell
2. Identical Bottles of Pills - GeeksForGeeks