Facebook, Lagrange and Dynamic Programming

What does Facebook, Lagrange and Dynamic Programming have in common? Well, they come up together in a technical interview question, by Daily Coding Problem:

Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given a positive integer n, find the smallest number of squared integers which sum to n.

For example, given n = 13, return 2 since 13 = 3² + 2² = 9 + 4.

Given n = 27, return 3 since 27 = 3² + 3² + 3² = 9 + 9 + 9.

There is actually a theorem about this problem: any positive number can be expressed as the sum of four integer squares - it is called the Lagrange's Four-Square Theorem:

Lagrange's four-square theorem

Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer squares.

But we can go one step beyond that and try to solve the problem not only for the power of two (square), but also for ANY positive power. I'll use Dynamic Programming to accomplish it.

The idea as always is to build the solution by construction rather than induction. So assume that you are solving the problem for some N, let's say that N = 27. Now suppose that you have already constructed the solution for all numbers from 0..26, so you have solution[0]...solution[26]. Awesome.

How can you now solve it for 27? Well, let's see:

• Maybe the solution for 27 is some solution prior plus 1^2. Hence, check whether solution[27-1^2] + 1 is the best so far.
• Maybe not, maybe you need to assume that the last item to be added to the solution is 2^2. Hence check whether solution[27-2^2] + 1 is the best solution so far.
• Maybe it isn't, hence check now solution[27-3^2] + 1.
• And we do that all the way to solution[27-5^2] + 1.
• Keep track of the best so far

That's it. The above algorithm is taking O(LogN). But we need to do that for all Ns from 1..N. Hence we're looking at O(NLogN). Notice that with this approach we can solve for any power, and the complexity will be the same just changing the base of the Log.

Hence, with this algorithm we can find the solution for say N = 312,117 and the power 2:

MinimPowerSum(312117, 2) = 3 (312117 = 415^2 + 374^2 + 4^2)

Or we can change the base to, say, 3:

MinimPowerSum(312117, 3) = 4 (312117 = 62^3 + 36^3 + 29^3 + 14^3)

Or even 5:

MinimPowerSum(312117, 5) = 9 (312117 = 9^5 + 9^5 + 9^5 + 9^5 + 9^5 + 7^5 + 2^5 + 2^5 + 1^5)

Code is down below and also over here on GitHub: https://github.com/BorisVasilenko/dailycodingproblem/blob/master/DailyCodingProblem02172019.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DailyCodingProblem
{
 class DailyCodingProblem02172019
 {
  public int MinimumPowerSum(int n, int power, bool printSum = false)
  {
   if (n == 0)
   {
    if (printSum)
    {
     Console.WriteLine("MinimPowerSum({0}, {1}) = {2} ({3} = {4})", n, power, 1, 0, "0^" + power.ToString());
    }
    return 1;
   }

   MapItem[] map = new MapItem[n + 1];

   map[0] = new MapItem();
   map[0].steps = 0;
   map[0].list = "";
   for (int i = 1; i <= n; i++)
   {
    map[i] = new MapItem();
    map[i].steps = Int32.MaxValue;
    map[i].list = "";
    for (int j = 1; Math.Pow(j, power) <= i; j++)
    {
     if (1 + map[i - (int)Math.Pow(j, power)].steps < map[i].steps)
     {
      map[i].steps = 1 + map[i - (int)Math.Pow(j, power)].steps;
      map[i].list = String.IsNullOrEmpty(map[i - (int)Math.Pow(j, power)].list) ? j.ToString() + "^" + power.ToString() : map[i - (int)Math.Pow(j, power)].list + " + " + j.ToString() + "^" + power.ToString();
     }
    }
   }

   if (printSum)
   {
    Console.WriteLine("MinimPowerSum({0}, {1}) = {2} ({3} = {4})", n, power, map[n].steps, n, map[n].list);
   }
   return map[n].steps;
  }

 }

 class MapItem
 {
  public int steps = 0;
  public string list = "";
 }
}