How can I manipulate an array to make the largest number?

Question

Say you have an array of positive integers, manipulate them so that the concatenation of the integers of the resultant array is the largest number possible. Ex: {9,1,95,17,5}, result: 9955171

Homework police: This was a google phone interview question and no NDAs were signed ;).

• user418748: Do we know anything about the numbers ? are they going to be in the range 0-100 ?
• Kakira: @Muggen no range. Just integers
• user418748: this excludes negatives and 0 I guess.
• Kakira: @Muggen yes. sorry about that, edited the question.
• bits: ok, maybe I do not understand lexicographical ordering. The wikipedia page is not very clear for integers. Can anyone explain what would be the lexicographic ordering of {5,54,56}? If it is {54,5,56} then my solution is based on lexicographical ordering of integers.

Answer 1

As others have pointed out, a lexicographic sort and concatenation is close, but not quite correct. For example, for the numbers 5, 54, and 56 a lexicographic sort will produce {5, 54, 56} (in increasing order) or {56, 54, 5} (in decreasing order), but what we really want is {56, 5, 54}, since that produces the largest number possible.

So we want a comparator for two numbers that somehow puts the biggest digits first.

1. We can do that by comparing individual digits of the two numbers, but we have to be careful when we step off the end of one number if the other number still has remaining digits. There are lots of counters, arithmetic, and edge cases that we have to get right.

2. A cuter solution (also mentioned by @Sarp Centel) achieves the same result as (1) but with a lot less code. The idea is to compare the concatenation of two numbers with the reverse concatenation of those numbers. All of the cruft that we have to explicitly handle in (1) is handled implicitly.

   For example, to compare 56 and 5, we'd do a regular lexicographic comparison of 565 to 556. Since 565 > 556, we'll say that 56 is "bigger" than 5, and should come first. Similarly, comparing 54 and 5 means we'll test 545 < 554, which tells us that 5 is "bigger" than 54.

Here's a simple example:

// C++0x: compile with g++ -std=c++0x <filename>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
int main() {
 std::vector<std::string> v = {
 "95", "96", "9", "54", "56", "5", "55", "556", "554", "1", "2", "3"
 };
 std::sort(v.begin(), v.end(),
 [](const std::string &lhs, const std::string &rhs) {
 // reverse the order of comparison to sort in descending order,
 // otherwise we'll get the "big" numbers at the end of the vector
 return rhs+lhs < lhs+rhs;
 });
 for (size_t i = 0; i < v.size(); ++i) {
 std::cout << v[i] << ' ';
 }
}

When run, this code displays:

9 96 95 56 556 5 55 554 54 3 2 1

• Alexander Malakhov: +1 for demonstrating C++0x lambdas. It makes std algorithms so Much more usable
• Alexander Malakhov: btw, your example {5, 56} is a bit unfortunate, since many posters here suggested descending ordering, which gives correct 565. Better example is {556, 55, 554} which doesn't work nor with ascending (55_554_556), nor with descending (556_554_55) lex ordering
• Nate Kohl: @Alexander Malakhov: excellent point. I've updated the example to use {5, 54, and 56}.
• Terminal: @Nate Kohl: your code fails for 6465 64 ideone.com/GboPL . Replace 0 in array index with i%rhsLen and i%lhsLen
• Terminal: @Nate Khol: i have edited the solution. You can recheck it if i missed something.

Answer 2

Looking at the example {5,54,56}, the proper way to order these numbers is when comparing strings A and B, we should consider lexicographic ordering of A+B with B+A.

For example:

• Comparing (5,54) becomes lexicographic comparison of ("554" with "545")
• Comparing (5,56) becomes lexicographic comparison of ("556" with "565")
• Comparing (54,56) becomes lexicographic comparison of ("5456" with "5654")

If we sort them this way, the resulting array is {56,5,54}.

Here's a Java implementation of this idea:

public class LexicographicSort implements Comparator<Integer> {
 public int compare(Integer o1, Integer o2) {
 String s1 = o1.toString();
 String s2 = o2.toString();
 return (s2+s1).compareTo(s1+s2);
 }
 public static void main(String[] args) {
 LexicographicSort ls = new LexicographicSort();
 Integer[] nums = {9,1,95,17,5};
 Arrays.sort(nums, ls);
 System.out.println(Arrays.toString(nums));
 }
}

• Sarp Centel: A similar question called "Studious Student" was asked at Facebook Hacker Cup 2011 Qualification Round. Given a list of words, you were asked to concatenate these words to generate the lexicographically lowest possible string. facebook.com/hackercup/problems.php?round=4

Answer 3

Well , for one you can try this

• split the numbers into individual characters
• sort them lexicographically in descending order
• concat the list

You got the largest number

• Mahesh: What do you mean by lexicographically ?
• Alexander Malakhov: I have had the same thought at first. Consider {98, 95, 9} - it's sorted as you suggest, but the result should be 9_98_95
• rajeshnair: @Alexander ,its sorted numerically but not lexicographically, See en.wikipedia.org/wiki/Lexicographic_preferences
• rajeshnair: Also see stackoverflow.com/questions/882954/…
• Alexander Malakhov: @Mahesh Lexicographical_order at wikipedia

Answer 4

Here is the implementation in c++

#include <stdio.h>
#include <sstream>
using namespace std;
/**
 a = 123
 b = 15
 v1 = 12315
 v2 = 15123
 return (v2 - v1) to make the function sort in descending order
*/
int compare_concatenated_ints(const void *arg1, const void *arg2)
{
 int v1 = *(int*) arg1;
 int v2 = *(int*) arg2;
 stringstream s1, s2;
 s1 << v1 << v2;
 s2 << v2 << v1;
 s1 >> v1;
 s2 >> v2;
 return (v2 - v1);
}
void print_array(int arr[], int count)
{
 for (int i = 0; i < count; ++i){
 printf("%d ", arr[i]);
 }
 printf("\n");
}
int main()
{
 int arr[] = {4, 0, 94, 9, 14, 0, 1}; 
 int count = sizeof(arr)/sizeof(arr[0]);
 printf("BEFORE\n");
 print_array(arr, count);
 std::qsort(arr, count, sizeof(int), compare_concatenated_ints);
 printf("AFTER\n");
 print_array(arr, count);
}

Answer 5

I guess it has already been solved. Here are few lines of code in Python using the logic already discussed in few of the answers:

>>li = [9,1,95,17,5]
>>li.sort(cmp=lambda a,b: cmp(int(str(a)+str(b)), int(str(b) + str(a))), reverse=True)
>>output = ""
>>for i in li:
output += str(i)
>>print output

Answer 6

Not sure if anyone is looking for a JavaScript solution, but if you are, here is the code

function LexicographicSort(input) {
 return Number(
 input
 .sort(function(a, b) {
// lexicographic sort
 return Number("" + b + a) - Number("" + a + b);
 })
 .join("")
 );
}

Answer 7

The idea of @Nate Kohl is very good. I just implemented a Java version using quicksort. Here it is:

import java.util.Random;
public class Sort_MaxConcatenation {
 private Random r = new Random();
 public void quicksort_maxConcatenation(int[] a, int begin, int end) {
 if (begin < end) {
 int q = partition(a, begin, end);
 quicksort_maxConcatenation(a, begin, q);
 quicksort_maxConcatenation(a, q + 1, end);
 }
 }
 private int partition(int[] a, int begin, int end) {
 int p = begin + r.nextInt(end - begin + 1);
 int t1 = a[p];
 a[p] = a[end];
 a[end] = t1;
 int pivot = t1;
 int q = begin;
 for (int i = begin; i < end; i++) {
 if (compare_maxConcatenation(a[i], pivot) > 0) {
 int t2 = a[q];
 a[q] = a[i];
 a[i] = t2;
 q++;
 }
 }
 int t3 = a[q];
 a[q] = a[end];
 a[end] = t3;
 return q;
 }
 private int compare_maxConcatenation(int i, int j) {
 int ij = Integer.valueOf(String.valueOf(i).concat(String.valueOf(j)));
 int ji = Integer.valueOf(String.valueOf(j).concat(String.valueOf(i)));
 if (ij > ji)
 return 1;
 else if (ij == ji)
 return 0;
 return -1;
 }
 public static void main(String[] args) {
 int[] a = new int[]{56, 5, 4, 94, 9, 14, 1};
 Sort_MaxConcatenation smc = new Sort_MaxConcatenation();
 smc.quicksort_maxConcatenation(a, 0, a.length-1);
 for(int i = 0;i < a.length;i++) {
 System.out.print(a[i]);
 }
 }
}

Answer 8

I would use the following function to sort them

class Kakira {
 static int preferred(int a, int b) {
 if(a == b) return a; // doesn't matter which
 String sa = a+"";
 String sb = b+"";
 for(int i = 0; i < sa.length() && i < sb.length(); i++) {
 char ca = sa.charAt(i);
 char cb = sb.charAt(i);
 if(ca < cb) return b;
 if(ca > cb) return a;
 }
 // we reached here - the larger one must start with the smaller one
 // so, remove the small one from the start of the small one, and
 // that will tell us which is most appropriate.
 if(a < b) {
 String choppedB = sb.substring(sa.length());
 if(preferred(Integer.parseInt(choppedB),a) == a) 
 return a;
 else
 return b;
 }
 else {
 String choppedA = sa.substring(sb.length());
 if(preferred(Integer.parseInt(choppedA),b) == b) 
 return b;
 else
 return a;
 }
 }
 // using a very simple sort because I'm being lazy right now
 public static void sort(int[] data) {
 while(!isSorted(data)) {
 for(int i = 0; i < data.length - 1; i++) {
 int a = data[i];
 int b = data[i+1];
 int p = preferred(a,b);
 if(p == b) {
 data[i] = b;
 data[i+1] = a;
 }
 }
 }
 }
 public static boolean isSorted(int[] data) {
 for(int i = 0; i < data.length - 1; i++) {
 int a = data[i];
 int b = data[i+1];
 int p = preferred(a,b);
 if(p != a) return false;
 }
 return true;
 }
 public static void main(String[] args) {
 int[] data = new int[]{9,1,95,17,5};
 sort(data);
 for(int i : data) System.out.print(i);
 System.out.println("");
 }
}

For the humans: First: I'm going to sort them using a special comparison function. This will put them in the most desired order, so we can just print them out.

I'm not worrying about the sort algorithm, because once you have the comparison you can use whatever sorting you want. The comparison is the important part.

So let's walk through the decision process.

First, if the two numbers are equal, no one cares which one it is. So we just return it.

Next, we get the string representation of the numbers so we can start comparing digits. We walk down the digits until we run out of digits on one of the strings. Once they are no longer equal, we want the one with the larger value, because we want high digits early (I think it's obvious why).

If we get to the end of one of the numbers and we don't yet have a winner, we know the longer one must start with the short one. They CAN'T be of equal length, because if the first digits are equal, and they're equal length, then the numbers themselves are equal, and they would have been caught earlier in the process. So the question is, which one goes first? Well, consider the ramifications:

12345 first: 12345123
123 first: 12312345

Obviously we want the first one. But how to know this? We take the 123 away from the long one. So we have 45 and 123.

Now, run these through the algorithm again, determine which was the winner, and whichever won the second round also wins the first round. If it were to go deeper, say (12312312 and 123) then it would continue to chain down.

Make sense?

• corsiKa: It took me about 20 minutes to debug it =) I'll add in the explanation.

Answer 9

Edit:

Create an array which contains all possible concats of the initial array

You get :

{91 , 19} When combining 1 and 9

{995 , 959} when 9 and 95

{917 , 179} when 9 and 17

from all those tuples get the higher number. and remove from the array the numbers that were used to make that concat string, and from the tuples remove all concats that use those numbers so as to avoid obvious mistake. Find the next big number in the tuples etc... etc...

---

I have a general idea as to how I would go about this, but I am not sure how to make it work for any other numbers bigger than 2 digits, maybe this will help you.

{9,1,95,17,5}

ok split the array into two arrays with one holding single digit numbers, and one holding the two digits.

sort them

you get {95 , 17} and {9,5,1}

compare if A1[0]+A2[0]> A2[0]+A1[0] lexicographically, eg 959> 995 ??? (+ in this case is not mathematical addition but string concat)

and get the bigger of those two

then you are left with 995 and {17} and {5,1} again, 175> 517 ?

you get 995-517 and you are left with {1}

Hope that helps

Answer 10

Interesting question. I suppose you could start with the simplest approach first, which would use brute force to create all possible numbers using recursion (depending on the problem & language this might have to be changed to iteration) and keep track of which one is the largest. For example {1, 83, 91} would give you { 18391, 19183, 83191, 83911, 91183, 91831 } from which you could determine 91831 as the largest number.

Using a solution which sorts the original numbers and concatenates the numbers in order has a pitfall in that if you have something like { 9, 82, 99 }, the sorted array would be { 99, 82, 9 }. However, this would result in 99829, when the largest number would actually be 99982.

Since the brute force solution works, but may not be optimal in terms of performance, it might be good to check out ways to optimize the solution (after profiling the original solution, of course). For example, you could start with a simple ordering scheme by multiplying individual digits of a number by the place they would occupy.

{ 9, 98, 95 }

The above set will result in a 5 digit number. We'll apply a simple formula which multiplies the individual digit by its place (1 for 1's place, 2 for 10's place, etc.) and sums them like so:

9 -> 9 * 5
98 -> 9 * 5 + 8 * 4
95 -> 9 * 5 + 5 * 4

which results in

9 -> 45
98 -> 77
95 -> 65

Now, as humans, we know that the 9 should come first, not 98 or 95. One way to fix this would them be to favor single digit numbers if the first digits of the candidates are identical (ie, favor 9 or 98/95/etc.). Generalizing a bit, you might choose the candidate with fewer digits each time if the digits from the left are larger or equivalent (if the number of digits is equal, use the above formula). If we have { 9871, 986 }, 9871 would have a higher value, but we would look at 986 and see that it has fewer digits.

9 8 7 1
| | | |
9 8 6

8 matches, continue, 7 is larger, so ignore 986 (9871986 versus the smaller 9869871). If the set were { 9861, 987 } instead:

9 8 6 1
| | | |
9 8 7

8 matches, continue, 7 is larger, so choose 987 (9879861 versus the smaller 9861987).

So testing this using the following set:

{ 7, 61, 811, 99 }

The result will be an 8 digit number. Applying the placement formula gives:

7 -> 7 * 8 = 56
61 -> 6 * 8 + 1 * 7
811 -> 8 * 8 + 1 * 7 + 1 * 6 = 77
99 -> 9 * 8 + 9 + 7 = 135

So 99 looks like it will go first, but now let's apply the second part of the algorithm by selecting the numbers with fewer digits:

7

7 is not identical with 9, of course, so we are left with 99 as the first number.

9 9 _ _ _ _ _

Next iteration:

7 -> 7 * 6 = 42
61 -> 6 * 6 + 1 * 5 = 41
811 -> 8 * 6 + 1 * 5 + 1 * 4 = 57

811 has the highest value and both 61 an 7 do not have identical digits from left to right so we insert 811.

9 9 8 1 1 _ _ _

Next iteration:

7 -> 7 * 3 = 21
61 -> 6 * 3 + 1 * 2 = 20

7 has the higher value and nothing has fewer digits--insert:

9 9 8 1 1 7 _ _

Next iteration:

Only one number (61) is left, so we'll insert it

9 9 8 1 1 7 6 1 -> 99811761

and get the biggest number! Note that if 61 had been something like 81, it would have correctly ended up in 811's spot -> 99818117 instead of the incorrect 99811817.

Answer 11

This is my solution though it might not be efficient. The code is in python1.3

#! /usr/bin/env python
def sort(arr):
 temparr = []
 for num in arr:
 l = len(str(num)) - 1
 n = num / pow(10, 1)
 temparr.append((n, num))
 temparr.sort()
 temparr.reverse()
 return [t[1] for t in temparr]
def buildNum(arr):
 finalNum = None
 for num in arr:
 snum = str(num)
 if not finalNum:
 finalNum = snum
 else:
 n1 = finalNum + snum
 n2 = snum + finalNum
 if n1 >= n2:
 finalNum = n1
 else:
 finalNum = n2
 return finalNum
def main():
 arr = [9,1,95,17,5]
 arr = sort(arr)
 print buildNum(arr)
main()

Answer 12

My strategy is to use any sorting algorithm with a custom compare function.

Before we dive into the code, here are some things to consider:

If the number of digits are equal, then the comparison is straight forward. But if the number of digits are unequal, then we extract the leftmost digit of the integer with more number of digits (and then compare recursively).

Code explains best. So, here is my working code:

int numDigits(int number)
{
 int digits = 0;
 if (number < 0) digits = 1; // remove this line if '-' counts as a digit
 while (number) {
 number /= 10;
 digits++;
 }
 return digits;
}
int comparator ( const void * elem1, const void * elem2 )
{
 int x = *(int *)elem1;
 int y = *(int *)elem2;
 if(x==y) return 0;
 int xLen = numDigits(x);
 int yLen = numDigits(y);
 if(xLen==yLen)
 {
 return x>y ? -1 : +1;
 }
 else
 {
 int xTens = pow((double)10,(double)xLen-1);
 int yTens = pow((double)10,(double)yLen-1);
 int xLeftmostDigit = (xTens != 0) ? x/xTens : 0;
 int yLeftmostDigit = (yTens != 0) ? y/yTens : 0;
 if( xLeftmostDigit == yLeftmostDigit )
 {
 if(xLen<yLen)
 {
 int yStrippedOutOfLeftmostDigit = y - yLeftmostDigit*yTens;
 return comparator(&x, &yStrippedOutOfLeftmostDigit);
 }
 else
 {
 int xStrippedOutOfLeftmostDigit = x - xLeftmostDigit*xTens;
 return comparator(&xStrippedOutOfLeftmostDigit, &y);
 }
 }
 else
 {
 return xLeftmostDigit > yLeftmostDigit ? -1 : +1;
 }
 }
 return false;
}

I wrote the above function specifically to be used with the stl's qsort.

This is my test code:

int main(int argv,char **argc) {
 //Ex: {9,1,95,17,5}, result: 9955171 
 int arr[] = {9,1,95,17,5};
 int arrLen = 5;
 for(int i=0; i<arrLen; i++)
 {
 cout << arr[i] << "_" ;
 }
 cout << endl;
 qsort(arr, 5, sizeof(int), comparator);
 for(int i=0; i<arrLen; i++)
 {
 cout << arr[i] << "_" ;
 }
 cout << endl;
}

• Alexander Malakhov: Since you are using C++ and not C (count<<, reference to STL)
• Alexander Malakhov: (Sorry, something with my browser) Since you are using C++ and not C (cout<<, reference to STL), why don't you use std::sort instead of qsort. It doesn't require casts between void* and int, and allows better inlining, which results in better performance
• Alexander Malakhov: 2. Why pow((double)10, ...) etc, what's wrong with implicit type conversions ? Also, you can write just 10.0 to get double constant. And I guess pow(double, int) will perform better, so your 2nd cast hurts performance. 3. Why don't you convert numbers to strings? I'm sure it will (once again) perform better (due to lesser number of divisions) and will make your code shorter and more clear (no need for xTens, shorter xLeftmostDigit and xStrippedOutOfLeftmostDigit definitions)
• Alexander Malakhov: 4. Last return in comparator is bool, whereas all previous are int. Also my 9 years old compiler (rightfully) marks this line as "unreachable", so you better just delete it
• Alexander Malakhov: Now regarding your algorithm. It will not work correctly for input {989, 91} (I've checked). That's because in recursive call you should strip out both numbers. That's a lot of notes, but please don't be offended. Just trying to help out

Answer 13

In C#

static void Concat(params int[] array)
{
 List<int> values = new List<int>(array);
 values.Sort((a, b) =>
 {
 StringBuilder asb = new StringBuilder(a.ToString());
 StringBuilder bsb = new StringBuilder(b.ToString());
 int lengthDiff = asb.Length - bsb.Length;
 if (lengthDiff == 0)
 return -a.CompareTo(b);
 else if (lengthDiff > 0)
 bsb.Append(bsb[bsb.Length - 1], lengthDiff);
 else
 asb.Append(asb[asb.Length - 1], -lengthDiff);
 return -asb.ToString().CompareTo(bsb.ToString());
 });

If you're familier with sign-extending bits, you can see this does exactly that only in reverse. It extends the shorter length number's last digit out to the same length and them simply returns the string comparison.

Answer 14

Okay, how about this algorithm , which uses compare function to check previous number and the number in the next index.For the sake of simplicity, i have used strings instead of integers.Though, the algorithm well explains what it is doing.

 #include<string>
 #include<iostream>
 #include<algorithm>
 using namespace std;
 int main(){
 bool arranged=false;
 string arr[]={"98","12","56","9"};
 for(int i=0;i<4;i++)
 cout<<arr[i]<<" ";
 cout<<endl;
while( arranged==false )
{ 
string previous = arr[0];
 arranged = true;
 for(int i = 1; i < 4;i++)
 { 
 string XY = (previous + arr[i] ); 
 string YX = (arr[i] + previous); 
 if ( YX.compare(XY) > 0 ) {
 swap(arr[i],arr[i-1]);
 arranged = false;
 }
 previous = arr[i]; 
 }
 }
 for(int i=0;i<4;i++)
 cout<<arr[i];
 return 0;
 } 

Answer 15

Here is the simple implementation in java without using comparator

import java.util.List;

import java.util.ArrayList;

import java.util.*;

import java.lang.Math;

public class LargestNumber{

public static void main(String args[]){
 ArrayList<Integer> al = new ArrayList<Integer>(); 
 al.add(872);
 al.add(625);
 al.add(92);
 al.add(8);
 al.add(71);
 Find find = new Find();
 find.duplicate(al);
 }

}

class Find{

public void duplicate(ArrayList<Integer> al){
 String numL ="";
 int size = al.size();
 Collections.sort(al,Collections.reverseOrder());
 ArrayList<Integer> arrL = new ArrayList<Integer>();
 for(int i = 0; i < size; i++){
 for(int j = 0; j < size - 1; j++){
 if((compare(al.get(j), al.get(j+1))) == 1){
 Collections.swap(al,j,j+1);
 }
 }
 }
 for(int i = 0; i < size; i++){
 numL = numL + al.get(i);
 }
 System.out.println(numL);
}
public static int compare(int x, int y){
 String xStr = String.valueOf(x);
 String yStr = String.valueOf(y);
 int a = Integer.parseInt(xStr+yStr);
 int b = Integer.parseInt(yStr+xStr);
 return (a>b)? 0:1;
}

}

Output 92887271625

Answer 16

Here is Python 3 solution where a is an array and n is the total number of element

def check(p,q):
 p=str(p)
 q=str(q)
 d=max(p+q,q+p)
 if d==p+q:
 return int(p),int(q)
 else:
 return int(q),int(p)
def find(a,n):
 for i in range(n):
 for j in range(n-1):
 c,d=check(a[j],a[j+1])
 a[j]=c
 a[j+1]=d
 print(*a,sep="")

Answer 17

This is a very simple C code with n in 1-100 range:

#include<stdio.h>
#include<math.h>
int main()
{
 int n;
 int arr[101];
 scanf("%d", &n);
 for (int i = 0; i < n; i++)
 scanf("%d", &arr[i]);
 for (int i = 0; i < n; i++)
 {
 for (int j = i + 1; j < n; j++)
 {
 int a = arr[i];
 int b = arr[j];
 int num_of_digits_a = 0;
 if (a == 0)
 {
 num_of_digits_a = 1;
 }
 else
 {
 while (a != 0)
 {
 a /= 10;
 num_of_digits_a++;
 }
 }
 int num_of_digits_b = 0;
 if (b == 0)
 {
 num_of_digits_b = 1;
 }
 else
 {
 while (b != 0)
 {
 b /= 10;
 num_of_digits_b++;
 }
 }
 long long int firstPossibility = pow(10, num_of_digits_a) * arr[j] + arr[i];
 long long int secondPossibility = pow(10, num_of_digits_b) * arr[i] + arr[j];
 if (firstPossibility > secondPossibility)
 {
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
 }
 }
 for (int i = 0; i < n; i++)
 printf("%d", arr[i]);
 return 0;
}