Largest int from concatenated ints
You are encouraged to solve this task according to the task description, using any language you may know.
Given a set of positive integers, the task is to write a function to order the integers in such a way that the concatenation of the numbers forms the largest possible integer and return this integer.
Use the following two sets of integers as tests and show your program output here.
- {1, 34, 3, 98, 9, 76, 45, 4}
- {54, 546, 548, 60}
- Possible algorithms
- A solution could be found by trying all combinations and return the best.
- Another way to solve this is to note that in the best arrangement, for any two adjacent original integers X and Y, the concatenation X followed by Y will be numerically greater than or equal to the concatenation Y followed by X.
- Yet another way to solve this is to pad ints to the same size by repeating the digits then sort using these repeated ints as a sort key.
Cf:
- Algorithms: What is the most efficient way to arrange the given numbers to form the biggest number?.
- Constructing the largest number possible by rearranging a list
C
<lang C>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
int catcmp(const void *a, const void *b) { char ab[32], ba[32]; sprintf(ab, "%d%d", *(int*)a, *(int*)b); sprintf(ba, "%d%d", *(int*)b, *(int*)a); return strcmp(ba, ab); }
void maxcat(int *a, int len) { int i; qsort(a, len, sizeof(int), catcmp); for (i = 0; i < len; i++) printf("%d", a[i]); putchar('\n'); }
int main(void) { int x[] = {1, 34, 3, 98, 76, 45, 4}; int y[] = {54, 546, 548, 60};
maxcat(x, sizeof(x)/sizeof(x[0])); maxcat(y, sizeof(y)/sizeof(y[0]));
return 0; }</lang>
- Output:
998764543431 6054854654
Clojure
<lang Clojure>(defn maxcat [coll]
(read-string
(apply str
(sort (fn [x y]
(apply compare
(map read-string [(str y x) (str x y)])))
coll))))
(prn (map maxcat [[1 34 3 98 9 76 45 4] [54 546 548 60]]))</lang>
- Output:
(998764543431 6054854654)
Haskell
Compare repeated string method
<lang Haskell>import Data.List (sortBy) import Data.Ord (comparing)
main = print (map maxcat [[1,34,3,98,9,76,45,4], [54,546,548,60]] :: [Integer])
where sorted = sortBy (flip $ comparing cycle)
maxcat = read . concat . sorted . map show</lang>
- Output:
[998764543431,6054854654]
Sort on comparison of concatenated ints method
<lang Haskell>import Data.List (sortBy)
main = print (map maxcat [[1,34,3,98,9,76,45,4], [54,546,548,60]] :: [Integer])
where sorted = sortBy (\a b -> compare (b++a) (a++b))
maxcat = read . concat . sorted . map show</lang>
- Output as above.
J
Solution: <lang j>maxlen=: [: >./ #&> maxnum=: (0 ". ;)@(\: maxlen $&> ])@(8!:0)</lang> Usage: <lang j> maxnum&> 1 34 3 98 9 76 45 4 ; 54 546 548 60 998764543431 6054854654</lang>
Java
This example sets up a comparator to order the numbers using Collections.sort as described in method #3 (padding and reverse sorting). It was also necessary to make a join method to meet the output requirements.
<lang java5>import java.util.*;
public class IntConcat {
private static Comparator<Integer> sorter = new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2){
String o1s = o1.toString();
String o2s = o2.toString();
if(o1s.length() == o2s.length()){
return o2s.compareTo(o1s);
}
int mlen = Math.max(o1s.length(), o2s.length());
while(o1s.length() < mlen * 2) o1s += o1s;
while(o2s.length() < mlen * 2) o2s += o2s;
return o2s.compareTo(o1s);
}
};
public static String join(List<?> things){
String output = "";
for(Object obj:things){
output += obj;
}
return output;
}
public static void main(String[] args){
List<Integer> ints1 = new ArrayList<Integer>(Arrays.asList(1, 34, 3, 98, 9, 76, 45, 4));
Collections.sort(ints1, sorter);
System.out.println(join(ints1));
List<Integer> ints2 = new ArrayList<Integer>(Arrays.asList(54, 546, 548, 60));
Collections.sort(ints2, sorter);
System.out.println(join(ints2));
}
}</lang> Output:
998764543431 6054854654
OCaml
<lang ocaml>let myCompare a b = compare (b ^ a) (a ^ b) let icsort nums = String.concat "" (List.sort myCompare (List.map string_of_int nums))</lang>
- testing
# icsort [1;34;3;98;9;76;45;4];; - : string = "998764543431" # icsort [54;546;548;60];; - : string = "6054854654"
Perl
<lang perl>sub maxnum {
join , sort { "$b$a" cmp "$a$b" } @_
}
print maxnum(1, 34, 3, 98, 9, 76, 45, 4), "\n"; print maxnum(54, 546, 548, 60), "\n";</lang>
- Output:
998764543431 6054854654
Perl 6
<lang Perl6>sub maxnum(@x) {
[~] sort -> $x, $y { $x~$y <=> $y~$x }, @x
}
say maxnum .[] for [<1 34 3 98 9 76 45 4>], [<54 546 548 60>];</lang>
- Output:
998764543431 6054854654
PHP
<lang php>function maxnum($nums) {
usort($nums, function ($x, $y) { return strcmp("$y$x", "$x$y"); });
return implode(, $nums);
}
echo maxnum(array(1, 34, 3, 98, 9, 76, 45, 4)), "\n"; echo maxnum(array(54, 546, 548, 60)), "\n";</lang>
- Output:
998764543431 6054854654
Python
Python: Sort on comparison of concatenated ints method
This also shows one of the few times where cmp= is better than key= on sorted()
<lang python>try:
cmp # Python 2 OK or NameError in Python 3
def maxnum(x):
return .join(sorted((str(n) for n in x),
cmp=lambda x,y:cmp(y+x, x+y)))
except NameError:
# Python 3
from functools import cmp_to_key
def cmp(x, y):
return -1 if x<y else ( 0 if x==y else 1)
def maxnum(x):
return .join(sorted((str(n) for n in x),
key=cmp_to_key(lambda x,y:cmp(y+x, x+y))))
for numbers in [(1, 34, 3, 98, 9, 76, 45, 4), (54, 546, 548, 60):
print('Numbers: %r\n Largest integer: %15s' % (numbers, maxnum(numbers)))</lang>
- Output:
Numbers: (1, 34, 3, 98, 9, 76, 45, 4) Largest integer: 998764543431 Numbers: (54, 546, 548, 60) Largest integer: 6054854654
REXX
<lang rexx>/*REXX pgm constructs largest integer from a list using concatenation.*/ @. = @.1 = '{1, 34, 3, 98, 9, 76, 45, 4}' @.2 = '{54, 546, 548, 60}'
/* [↓] process all the lists. */
do j=1 while @.j\==; $= /*keep truckin' until exausted. */
z=space(translate(@.j,,'{,}')) /*perform some scrubbing on list.*/
do while z\== /*examine each*/
$=$ || mx() /*get "max" #.*/
end /*while*/
say right($,30) ' max for: ' @.j
end /*j*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────MX subroutine───────────────────────*/ mx: procedure expose z; big=word(z,1); index=1
do k=2 to words(z); x=word(z,k) /*get a num. */
L=max(length(big),length(x)) /*get max len*/
if left(x,L,left(x,1))>>left(big,L,left(big,1)) then do
big=x
index=k
end
end /*k*/
z=strip(delword(z,index,1)) return big</lang> output when using the input of: xxx
998764543431 max for: {1, 34, 3, 98, 9, 76, 45, 4}
6054854654 max for: {54, 546, 548, 60}
Python: Compare repeated string method
<lang python>def maxnumx(x):
maxlen = len(str(max(x)))
return .join(sorted((str(n) for n in x), reverse=True,
key=lambda i: i*(maxlen // len(i) + 1)))
for numbers in [(1, 34, 3, 98, 9, 76, 45, 4), (54, 546, 548, 60)]:
print('Numbers: %r\n Largest integer: %15s' % (numbers, maxnum(numbers)))</lang>
- Output as above.
Python: Try all permutations method
<lang python>from itertools import permutations def maxnumx(x):
return max(int(.join(n) for n in permutations(str(i) for i in x)))
for numbers in [(1, 34, 3, 98, 9, 76, 45, 4), (54, 546, 548, 60)]:
print('Numbers: %r\n Largest integer: %15s' % (numbers, maxnum(numbers)))</lang>
- Output as above.
Ruby
Sort on comparison of concatenated ints method
<lang Ruby>def icsort nums
nums.sort { |x, y| "#{y}#{x}" <=> "#{x}#{y}" }
end
[[54, 546, 548, 60], [1, 34, 3, 98, 9, 76, 45, 4]].each do |c|
p c # prints nicer in Ruby 1.8 puts icsort(c).join
end</lang>
- Output:
[54, 546, 548, 60] 6054854654 [1, 34, 3, 98, 9, 76, 45, 4] 998764543431
Compare repeated string method
<lang ruby>def icsort nums
maxlen = nums.max.to_s.length
nums.map{ |x| x.to_s }.sort_by { |x| x * (maxlen / x.length + 1) }.reverse
end
[[54, 546, 548, 60], [1, 34, 3, 98, 9, 76, 45, 4]].each do |c|
p c # prints nicer in Ruby 1.8 puts icsort(c).join
end</lang>
- Output as above.
Run BASIC
<lang runbasic>a1$ = "1, 34, 3, 98, 9, 76, 45, 4" a2$ = "54,546,548,60"
print "Max Num ";a1$;" = ";maxNum$(a1$) print "Max Num ";a2$;" = ";maxNum$(a2$)
function maxNum$(a1$) while word$(a1$,i+1,",") <> ""
i = i + 1 a$(i) = trim$(word$(a1$,i,","))
wend
s = 1 while s = 1
s = 0 for j = 1 to i -1 if a$(j)+a$(j+1) < a$(j+1)+a$(j) then h$ = a$(j) a$(j) = a$(j+1) a$(j+1) = h$ s = 1 end if next j
wend
for j = 1 to i
maxNum$ = maxNum$ ; a$(j)
next j
end function</lang>Output
Max Num 1, 34, 3, 98, 9, 76, 45, 4 = 998764543431 Max Num 54,546,548,60 = 6054854654
Tcl
<lang tcl>proc intcatsort {nums} {
lsort -command {apply {{x y} {expr {"$y$x" - "$x$y"}}}} $nums
}</lang> Demonstrating: <lang tcl>foreach collection {
{1 34 3 98 9 76 45 4}
{54 546 548 60}
} {
set sorted [intcatsort $collection] puts "\[$collection\] => \[$sorted\] (concatenated: [join $sorted ""])"
}</lang>
- Output:
[1 34 3 98 9 76 45 4] => [9 98 76 45 4 34 3 1] (concatenated: 998764543431) [54 546 548 60] => [60 548 546 54] (concatenated: 6054854654)
Vim Script
This solution is intended to be run as an Ex command within a buffer containing the integers to be processed, one per line. <lang Vim>%s/\(.\+\)/\1\1/ | sort! | %s/\(.\+\)\1\n/\1/</lang>
- Demonstration
<lang Bash>$ paste -s nums 1 34 3 98 9 76 45 4 $ vim -S icsort.vim nums 998764543431</lang>