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 ;).
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.
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
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:
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));
}
}
Well , for one you can try this
You got the largest number
#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);
}
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
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("")
);
}
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]);
}
}
}
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?
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
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.
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()
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;
}
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.
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;
}
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
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="")
