how to improve this code?

Question

I have developed a code for expressing the number in terms of the power of the 2 and I am attaching the same code below.

But the problem is that the expressed output should of minimum length.

I am getting output as 3^2+1^2+1^2+1^2 which is not minimum length. I need to output in this format:

package com.algo;
import java.util.Scanner;

public class GetInputFromUser {
    public static void main(String[] args) {
    // TODO Auto-generated method stub
        int n;
        Scanner in = new Scanner(System.in);

        System.out.println("Enter an integer");
        n = in.nextInt();

        System.out.println("The result is:");
        algofunction(n);
    }

    public static int algofunction(int n1)
    {
        int r1 = 0;
        int r2 = 0;
        int r3 = 0;
        //System.out.println("n1: "+n1);
        r1 = (int) Math.sqrt(n1);
        r2 = (int) Math.pow(r1, 2);
        // System.out.println("r1: "+r1);
        //System.out.println("r2: "+r2);
        System.out.print(r1+"^2");

        r3 = n1-r2;
        //System.out.println("r3: "+r3);
        if (r3 == 0)
            return 1;

        if(r3 == 1)
        {
            System.out.print("+1^2");
            return 1;
        } 
        else {
            System.out.print("+");
            algofunction(r3);
            return 1;
        }
    }
}

Answer 1

Dynamic programming is all about defining the problem in such a way that if you knew the answer to a smaller version of the original, you could use that to answer the main problem more quickly/directly. It's like applied mathematical induction.

In your particular problem, we can define MinLen(n) as the minimum length representation of n. Next, say, since we want to solve MinLen(12), suppose we already knew the answer to MinLen(1), MinLen(2), MinLen(3), ..., MinLen(11). How could we use the answer to those smaller problems to figure out MinLen(12)? This is the other half of dynamic programming - figuring out how to use the smaller problems to solve the bigger one. It doesn't help you if you come up with some smaller problem, but have no way of combining them back together.

For this problem, we can make the simple statement, "For 12, it's minimum length representation DEFINITELY has either 1^2, 2^2, or 3^2 in it." And in general, the minimum length representation of n will have some square less than or equal to n as a part of it. There is probably a better statement you can make, which would improve the runtime, but I'll say that it is good enough for now.

This statement means that MinLen(12) = 1^2 + MinLen(11), OR 2^2 + MinLen(8), OR 3^2 + MinLen(3). You check all of them and select the best one, and now you save that as MinLen(12). Now, if you want to solve MinLen(13), you can do that too.

Advice when solo: The way I would test this kind of program myself is to plug in 1, 2, 3, 4, 5, etc, and see the first time it goes wrong. Additionally, any assumptions I happen to have thought were a good idea, I question: "Is it really true that the largest square number less than n will be in the representation of MinLen(n)?"

Your code:

r1 = (int) Math.sqrt(n1);
r2 = (int) Math.pow(r1, 2);

embodies that assumption (a greedy assumption), but it is wrong, as you've clearly seen with the answer for MinLen(12).

Instead you want something more like this:

public ArrayList<Integer> minLen(int n)
{
    // base case of recursion
    if (n == 0)
        return new ArrayList<Integer>();

    ArrayList<Integer> best = null;
    int bestInt = -1;
    for (int i = 1; i*i <= n; ++i)
    {
        // Check what happens if we use i^2 as part of our representation
        ArrayList<Integer> guess = minLen(n - i*i);

        // If we haven't selected a 'best' yet (best == null)
        // or if our new guess is better than the current choice (guess.size() < best.size())
        // update our choice of best
        if (best == null || guess.size() < best.size())
        {
            best = guess;
            bestInt = i;
        }
    }

    best.add(bestInt);
    return best;
}

Then, once you have your list, you can sort it (no guarantees that it came in sorted order), and print it out the way you want.

Lastly, you may notice that for larger values of n (1000 may be too large) that you plug in to the above recursion, it will start going very slow. This is because we are constantly recalculating all the small subproblems - for example, we figure out MinLen(3) when we call MinLen(4), because 4 - 1^2 = 3. But we figure it out twice for MinLen(7) -> 3 = 7 - 2^2, but 3 also is 7 - 1^2 - 1^2 - 1^2 - 1^2. And it gets much worse the larger you go.

The solution to this, which lets you solve up to n = 1,000,000 or more, very quickly, is to use a technique called Memoization. This means that once we figure out MinLen(3), we save it somewhere, let's say a global location to make it easy. Then, whenever we would try to recalculate it, we check the global cache first to see if we already did it. If so, then we just use that, instead of redoing all the work.

import java.util.*;

class SquareRepresentation
{
    private static HashMap<Integer, ArrayList<Integer>> cachedSolutions;
    public static void main(String[] args)
    {
        cachedSolutions = new HashMap<Integer, ArrayList<Integer>>();
        for (int j = 100000; j < 100001; ++j)
        {
            ArrayList<Integer> answer = minLen(j);
            Collections.sort(answer);
            Collections.reverse(answer);
            for (int i = 0; i < answer.size(); ++i)
            {
                if (i != 0)
                    System.out.printf("+");
                System.out.printf("%d^2", answer.get(i));
            }
            System.out.println();
        }
    }

    public static ArrayList<Integer> minLen(int n)
    {
        // base case of recursion
        if (n == 0)
            return new ArrayList<Integer>();

        // new base case: problem already solved once before
        if (cachedSolutions.containsKey(n))
        {
            // It is a bit tricky though, because we need to be careful!
            // See how below that we are modifying the 'guess' array we get in?
            // That means we would modify our previous solutions! No good!
            // So here we need to return a copy
            ArrayList<Integer> ans = cachedSolutions.get(n);
            ArrayList<Integer> copy = new ArrayList<Integer>();
            for (int i: ans) copy.add(i);
            return copy;
        }

        ArrayList<Integer> best = null;
        int bestInt = -1;
        // THIS IS WRONG, can you figure out why it doesn't work?:
        // for (int i = 1; i*i <= n; ++i)
        for (int i = (int)Math.sqrt(n); i >= 1; --i)
        {
            // Check what happens if we use i^2 as part of our representation
            ArrayList<Integer> guess = minLen(n - i*i);

            // If we haven't selected a 'best' yet (best == null)
            // or if our new guess is better than the current choice (guess.size() < best.size())
            // update our choice of best
            if (best == null || guess.size() < best.size())
            {
                best = guess;
                bestInt = i;
            }
        }

        best.add(bestInt);

        // check... not needed unless you coded wrong
        int sum = 0;
        for (int i = 0; i < best.size(); ++i)
        {
            sum += best.get(i) * best.get(i);
        }
        if (sum != n)
        {
            throw new RuntimeException(String.format("n = %d, sum=%d, arr=%s\n", n, sum, best));
        }

        // New step: Save the solution to the global cache
        cachedSolutions.put(n, best);

        // Same deal as before... if you don't return a copy, you end up modifying your previous solutions
        // 
        ArrayList<Integer> copy = new ArrayList<Integer>();
        for (int i: best) copy.add(i);
        return copy;
    }
}

It took my program around ~5s to run for n = 100,000. Clearly there is more to be done if we want it to be faster, and to solve for larger n. The main issue now is that in storing the entire list of results of previous answers, we use up a lot of memory. And all of that copying! There is more you can do, like storing only an integer and a pointer to the subproblem, but I'll let you do that.

And by the by, 1000 = 30^2 + 10^2.