For example if I take the number 4544, then the maximum product I get is 2376 when I rearrange the digits as 5444.

example: (5444) = 2376 is greater than (4544) = 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?

Thank you!

CodePudding user response：

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) and minimise A (using the remaining smaller digits). 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.

CodePudding user response：

One approach can be two find two highest digits, and keeping them in the left most place and than do the opposite for remaining 2nd place.

for example:

if you have number 1234, the highest digits are 3 and 4 so lets keep them on first position, and for remaining 2 do the same so numbers will be:

(41*32) = 1312

so here you see 1312 is highest number possible