How to form the biggest number from an array of numbers

Question

Given an array of numbers, I need to arrange them in a way that yields the largest value.

For example, if the given numbers are {3, 1, 13, 34,8}, the arrangement 8343131 gives the largest value. And if the given numbers are {1, 34, 3, 98, 9, 76, 45, 4}, then the arrangement 998764543431 gives the largest value.

$array = array("3", "1", "13", "34", "8");

needs to have output is as follows

OUTPUT:
8343131

Using PHP how can I achieve that?

score 0 · Accepted Answer · answered Dec 16 '17 at 10:28

0

Find all possible combination of given array values and find max

function permute($arg) {
    $array = is_string($arg) ? str_split($arg) : $arg;
    if(1 === count($array))
        return $array;
    $result = array();
    foreach($array as $key => $item)
        foreach(permute(array_diff_key($array, array($key => $item))) as $p)
            $result[] = $item . $p;
    return $result;
}

$array = array("3", "1", "13", "34", "8");

echo max(permute($array));

Live demo : https://eval.in/920239

Output is : 8343131

answered Dec 16 '17 at 10:28

Niklesh Raut

34,013
16
75
109

This has a very bad time and space complexity. I guess it is something like O(n!) for both the time and space. To illustrate, note how a simple array with all 10 digits makes the algorithm run out of allowed clock time on [eval.in](https://eval.in/920368). On [repl.it](https://repl.it/@trincottrincots/maximiseNumberOutOfSpace) the same input makes it run out of allowed space (134 MB). Adding more elements to the input will make it soon impossible to run on a standard PC. This can be done much more efficiently. – trincot Dec 16 '17 at 14:16

score 0 · Answer 2 · answered Dec 16 '17 at 10:30

0

I assume that whay you want is to create the biggest possible number using the digits of the strings in the array.

The easiest way to achieve this is to create an array with all the digits and order it from highest to lowest, then create a number using those digits:

$array = array("3", "1", "13", "34", "8");

$tmp = array();
foreach ($array as $i)
    $tmp = array_merge($tmp, str_split($i, 1));

rsort($tmp, SORT_NUMERIC);

$maxNumber = implode('', $tmp);

This will output 8433311, the biggest number possible with the digits of the strings provided.

answered Dec 16 '17 at 10:30

Koas

402
3
10

1

That's not the expected result, it should be `8343131` instead – Spoody Dec 16 '17 at 10:33
Thnx for the answer, but user2486 given the answer which i wanted. – Tarzy Dec 16 '17 at 10:37
That's right, the original question was not as detailed as the current one, I solved the wrong problem :) – Koas Dec 16 '17 at 10:37

trincot · Answer 3 · 2017-12-17T14:22:46.757

It is not needed to check all permutations. I think this can be solved in O(k.n.log(n)) time where n is the array size and k is the number of characters in the longest string.

The idea is that the strings should be sorted by padding them first so all have the same length. The padding should happen by repeating the original string after itself as many times as necessary and then clipped to a common length. When that length is taken to be the double length of the largest string then the result will be fine.

Take for instance this input:

["1", "1112", "11121", "111230", "385", "38530"]

Then the algorithm would extend those strings as follows:

["111111111111","111211121112","111211112111","111230111230","385385385385","385303853038"]

Sorted in descending order this gives:

["385385385385","385303853038","111230111230","111211121112","111211112111","111111111111"]

Converted back to their original values:

["385", "38530", "111230", "1112", "11121", "1"]

which gives the result:

"385385301112301112111211"

Here is the code for that:

$array = ["1", "1112", "11121", "111230", "385", "38530"];
$maxlen = 2 * max(array_map('strlen', $array));
$padded = array_map(function ($a) use ($maxlen) {
    return substr(str_repeat($a, ceil($maxlen / strlen($a))), 0, $maxlen);
}, $array);
array_multisort($padded, SORT_DESC, $array);
$result = implode("", $array);

echo $result;

Unlike the accepted answer, this also works in reasonable time for arrays which have more than a few values:

See it run on eval.in for input:

["3", "1", "7", "8", "9", "2", "4", "6", "5", "0", "15", "29", "32", "41", 
 "551", "56", "671", "6713", "782", "7820", "88", "880", "91", "9121"]

It outputs:

991912188888078278207671671365655514413322921510

How to form the biggest number from an array of numbers

3 Answers3