SRM 597, D2, 250-Pointer (LittleElephantAndDouble)

James S. Plank

Sun Aug 28 14:14:17 EDT 2016
The first step to solving this problem is to sort the input vector.

Now, since the vector is sorted, you can start with the first element, and see whether you can double it until it equals the second element, or is greater than the second element. If greater, then the answer is "NO". If equal, then you can move on to the second element.

With the second element, you keep doubling it until it is equal to or greater than the third element.

And so on. Once again, the key step was sorting the input. This lets you know that each element is less than or equal to the next element, and you can keep doubling it. If you didn't sort, then you'd have to do more work to figure out which elements to double.


You should ask yourself two questions before you hit SUBMIT:
  1. Will this be too slow? The answer is no, because you can double at most 30 times before you hit 109 (which roughly equals 230).
  2. Should I be worried about integer overflow. As it turns out, no. The maximum integer is (231-1), which is roughly 2,000,000,000. A little larger, actually. The maximum value that you'll get to double is 999,999,999, and that doubled is less than 2,000,000,000. You're good.

My Solution.