Cooking The Books

You are given a number $$N$$ with $$0 \leq N \leq 999,999,999$$. $$N$$ will not have any leading zeroes. You are allowed to swap at most one pair of digits of $$N$$ to make a new number $$M$$ ($$M$$ must not have leading zeroes). What is the minimum $$M$$ you can make from this process? Also, what is the maximum $$M$$ you can make from this process?
  1. Brute force
  2. Small number of digits
  3. Treat $$N$$ as a string
  4. All numbers have the same length (cannot delete or add characters)
  5. Lexicographical comparison
  6. Greed

There are many ways to solve this problem. The most clever solution is "greedy": Try to swap the first digit with the largest (respectively, smallest) remaining digit. If that works, then you're done (this must be the largest number you can get with a single swap). Otherwise, you have to do a bit more work. I will leave this part as an exercise to describe the complete greedy solution (see the Related Problems section below).

In general, this "greedy" solution works very efficiently (I think it can be made to run in $$O(|N|)$$ time, where $$|N|$$ is the number of digits in the number $$N$$). But you must be extra careful for special cases and minor details. Even though this was technically the "easiest" problem on the contest (Facebook Hacker Cup) more people failed this problem than the next problem! Why? Because this greedy solution (the "clever") solution, is very hard to code correctly on your first try unless you are careful!

Alternatively, I chose not to do a greedy solution. I chose to do a "stupid brute force" solution. We observe that $$N$$ is at most $$999,999,999$$, so $$N$$ will have at most $$9$$ digits. So there will be at most $$\binom{9}{2} = 45$$ pairs of digits that we can choose to swap (this is the "binomial coefficient", pronounced "nine, choose two"). Our "answer" must result from swapping one of these pairs, so why not try all of them!?. After each swap, we check if it is the maximum or minimum number seen so far, and remember this if so. Then we "undo" the swap, and try another pair. We repeat this until we have tried all solutions. This is called an "Exhaustive Search" algorithm.

The pseudo-code for an exhaustive search would be:


  digit(N,i):
    return the ith digit of N

  def solve(N):
    low := N    # keep track of minimum number seen so far
    high := N    # keep track of maximum number seen so far
  
    Let k := number of digits in N
    for i = 1..N:
      for j = i+1..N:
      if (i==1 and digit(N,j) == '0'):
        skip this i and j       # avoid creating leading zeroes
      else:
        swap digit(N,j) with digit(N,i)
		
        if (N < low) : set low = N			#>
        if (N < high): set high = N			#>
		
        un-swap digit(N,j) with digit(N,i)
        
  print low, high

There is one tricky implementation detail: how do we quickly access the "digits" of $$N$$? Interestingly enough, I decided to store $$N$$ as a "string" rather than as an integer! As a string you can easily access and modify the $$i^{th}$$ digit like you would with an array. In C++, I just declared $$N$$ as type $$string$$. If you treat $$N$$ as an integer, you have to do complicated arithmetic (division by powers of 10, modulus operations, etc.) to get access to a particular digit. It's not much harder, but it is a bit more error-prone!

Now, "Exhaustive Search" is really slow: this algorithm takes $$O(|N|^3)$$ time approximately, which is much slower than $$O(N)$$. But, it can be implemented very quickly and with a very little chance of making an error. By exploiting the constraints, we were able to recognize that a "stupid" solution is actually much "smarter" in this case, than the clever "greedy" solution!

  1. $$|N|$$ is small. This means a brute force solution would pass.
  2. There are at most $$\binom{9}{2}$$ choices of pairs to swap. So we can try all of them, and keep track of the min/max.
  3. If $$N$$ is stored as a string, it is easier to access the digits and perform comparisons
  1. Early on, before spending time thinking about how to solve the problem, I wrote down and considered all of the data. In this particular case, the value of $$|N|$$ was always guaranteed to be small. This immediately implied that I could do a "stupid solution" without worrying about efficiency.
  2. "Keep it Simple Stupid" (KISS). This is a phrase I've heard before in my training. In general, under time pressure, the "stupidest solution that works" is often the best choice. This takes intuition and experience to know when this applies.
  3. A number is technically a "string" in some ways. I treated $$N$$ as a string in my code so that I could easily access the digits without doing any arithmetic. To compare to "numbers" with the same number of digits is the same as comparing two "string" using the $$\lt$$ operator in most languages (be careful that they are the same length). So I had very little work to do.
  • "Keep it Simple Stupid" and "Exploit the Constraints". These "catch-phrases" can help minimize your risk of errors, save you time, and increase your chance of getting AC/Accepted on the first try.
  • Brute Force / Exhaustive Search
  • Greedy / Observation
  • Sorting and Comparisons