Solution to "Squary Numbers"

View Problem: Squary Numbers

We will solve this problem by using a Dynamic Programming (DP) approach. Let us assume the number N is given to us in a string format s[1..L] where L is the number of digits in N. s[i..j] denotes the sub-string starting at index i (inclusive) and ending at index j (again inclusive).

s[i..j] is Squary if and only if for at least one k in [i..j-1], both s[i..k] and s[k+1..j] are Squary. This is our sub-problem for the Dynamic Programming approach:

dp[1..L][1..L] = 0;

for(i=1; i<=L; i++)
{
    for(j=i; j<=L; j++)
    {
        if(isPerfectSquare(s[i..j]))
        {
            dp[i][j] = 1;
        }
    }
}

for(l=1; l<=L; l++)
{
    for(i=1; i<=L-l+1; i++)
    {
        j = i+l-1;

        for(k=i; k<=j-1; k++)
        {
            if(dp[i][k] == 1 && dp[k+1][j] == 1)
            {
                dp[i][j] = 1;
            }
        }
    }
}

dp[i][j] = 1 only if s[i..j] is Squary, otherwise dp[i][j]=0. So, if dp[1][L] = 1, then N is Squary, otherwise it isn't.

To find a valid partitioning for a Squary number, we use the following simple recursive algorithm:

partitions(i, j, s, dp)
{
    if(isPerfectSquare(s[i..j]))
    {
       return(pair(i,j)); 
    }
    else
    {
        for(k=i; k<=j-1; k++)
        {
            if(dp[i][k] == 1 && dp[k+1][j] == 1)
            {
                return(partitions(i, k, s, dp) + partitions(k+1, j, s, dp));
            }
        }
    }
}

Calling partitions(1, L, s, dp) will return a set of pairs of indices denoting the starting and ending indices of all the partitions.