How to arrange the digits of a number such that when I break it into two numbers of equal digits the product of the two numbers is maximum?

Question

Example: If I take the number 4544, then the maximum product I get is 2376 when I rearrange the digits as 5444. (54 x 44) = 2376 which is greater than (45 x 44) = 1980

My approach for solving the problem was to permute the number in all possible ways, divide it into two parts and then find the max product from there. Is there a faster way to solve the problem or is a completely different approach to the problem is possible?

Here's my code:

 import java.util.*;
class MaxProduct
{
    static int maxprod = 0;
    public static void main(String args[])
    {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter a no");
    String n = sc.next();
    permute(n,0);
    System.out.println("Max Product is "+maxprod);
    }
    public static void permute(String s,int i)
    {
             if( i==s.length()-1)
         {
            int a = Integer.parseInt(s.substring(0,i/2+1));
            int b = Integer.parseInt(s.substring(i/2+1));
            maxprod = Math.max(a*b,maxprod);
         }
            else 
            {
            for(int k=i;k<s.length();k++)
                {
                          s =swapelement(s,k,i); 
                          permute(s,i+1);
                          s=swapelement(s,k,i);
            }
            }
    }
       public static String swapelement(String a,int i, int j)
            {
                char x[]=a.toCharArray();
                char ch = x[i];
                x[i]=x[j];
                x[j]=ch;
                return String.valueOf(x);
            }
}

Thank you!

Answer 1

Let's look at a smaller problem first. For variables x,y, you are given

x + y = c (constant)

The question is, when will x*y be maximum? It can be solved in many ways, one of them being differential math. Long story short, the closer x and y are to each other, the larger their product is.

How to apply this to your problem?

1. Take the largest digits in the set, assign them to the numbers (let them be A and B)
2. As soon as one number becomes bigger than the other (let A>B), assign the remaining digits to maximise B (larger digits in descending order). For A we use the remaining smaller digits to make the largest number out of them. Assigning the larger digits to B is done to make it closer to A.

Example #1

Number = 123456 Taking largest digits, A = 6 and B = 5. Now, we will greedily maximise B, so the numbers become A = 621 and B = 543

Example #2

Number = 88871256 Taking largest digits, A = 8 and B = 8. Since they're still equal, we repeat step 1, so A = 88 and B = 87. Now, we will greedily maximise B, so the numbers become A = 8821 and B = 8765.

Since this is a rather straightforward problem, adding any implementation seems unnecessary.