Problem: Given an array of positive integers that can contain duplicates, find the minimum number obtained by concatenating the integers. Ex: `[3, 32, 321]`

returns `321323`

Aside from trying all n! concatenation permutations, I can't seem to find a good way to solve this. I do know of a good solution below, but I'm having trouble understanding why it's true (**stop reading here if you want to try and solve this**):

I've a read a solution where we can sort the array with a comparator that compares two numbers `m`

and `n`

by comparing the numerical values of the concatenation `mn`

and the concatenation `nm`

, and the sorted array will be the concatenation that gives the mininum number, but I can't figure out why this is true. Any ideas?

You can use something similar to bubble sort to solve this.

First, we notice that the length of the final result is fixed.

Second, the result is the minimum lexicographical string that you can create (as the length of all possible string is fixed, so the minimum lexicographical is also the minimum number).

Assume that we have two number `n`

and `m`

, and if nm < mn, so n should always be in front of m. Because if we have a string is m...n, so we can always obtain a smaller string by swapping this into n...m.

So we continue to swapping number until nothing can be swapped, and this is the final answer

This is more a math problem than a computer problem.

Define the concatenation operation as C(a1, ... an), where (a1, ... an) is an ordered array. Then C satisfies that

C(a1, ... an) = C( C(a1, ... ax), C(a(x + 1), ... an) )

for any 1 < x < n.

Using Mathematical Induction, define F as a function working on array of n variables.

F(2) = min(C(a1, a2), C(a2, a1)) is well defined.

For F(n), given F(n - 1) is minimized, the problem becomes to find the best position for an so that F(n) is minimized. Then it's easy to show that

For any ax that C(ax, an) > C(an, ax), C(a1, ... ax, an, a(x+1), ... a(n - 1)) < C(a1, ... a(x - 1), an, ax, a(x+1), ... a(n - 1)).

For any ax that C(ax, an) < C(an, ax), C(a1, ... ax, an, a(x+1), ... a(n - 1)) > C(a1, ... a(x - 1), an, ax, a(x+1), ... a(n - 1)).

So the best solution is insert an at where C(ax, an) < C(an, ax) and C(a(x+1), an) > C(an, a(x + 1)). Thus the algorithm you described holds.

If they were all single digit numbers, the solution is simple: sort them and pick the smallest digits for the most significant (leftmost digits) in the result. e.g. pick 2 before 3 cause 23 is less than 32.

Similar for multi digit numbers, sort by leftmost digit. e.g. pick 123 before 45, since 12345 is less than 45123.

The trickiest part is for ties. If the leftmost digit is the same, compare the 2nd digit, then the third... e.g. pick 321 before 34 since 32134 is less than 34321.

Finally, what if there is a tie and you run out of digits? Pick 321 before 3 since 3213 is less than 3321.

So, using Java as a language, write a Comparator using these rules (note that you are probably better treating the numbers as Strings, not numbers), sort, then concatenate. Other languages would be similar.

**Java code for the Comparator:** See also Gist with a main() for testing Note that I was able to reorg and simplify the rules. This code can probably be better optimized for speed. (Note: assumes all the ints are first converted to Strings for efficiency)

```
public class SO25396760 implements Comparator<String> {
@Override
public int compare(String s1, String s2) {
int minLength = Math.min(s1.length(), s2.length());
int result = s1.substring(0, minLength).compareTo(s2.substring(0, minLength));
if (result != 0)
return result;
int lenDiff = s1.length() - s2.length();
if (lenDiff == 0)
return 0; // Strings are equal
if (lenDiff < 0)
return compare(s1, s2.substring(minLength));
else
return compare(s1.substring(minLength), s2);
}
}
```

When input is {"321","3","35", "321334", "333", "2"}; the sorted array is [2, 321, 321334, 3, 333, 35] and the concatenated value is 2321321334333335. Test by inspection that this is minimal.

Let `<'`

be the comparator in question, so that `m <' n`

if and only if `mn < nm`

. *Assuming that <' is a strict weak ordering*, the other answers are on the right track about why sorting by

`<'`

is a good idea. Here’s a careful proof. Suppose to the contrary that two (possibly nonadjacent) input strings `m <' n`

are out of order, so that the output looks like```
...n...p...m...
```

By induction on the distance between `n`

and `m`

, we show that this output is not the minimum. In the base case, when `n`

is next to `m`

, we can swap them. Since `mn < nm`

, the new output is smaller. Inductively, let `p`

be an input string appearing in the output between `n`

and `m`

. If `p <' m`

, then `p <' n`

by transitivity. If `p <' n`

, then we invoke the inductive hypothesis on `n`

and `p`

, which are closer than `n`

and `m`

. If `n <' p`

, then `m <' p`

by transitivity. If `m <' p`

, then we invoke the inductive hypothesis on `p`

and `m`

, which are closer than `n`

and `m`

. If none of these cases applies, then `n`

and `p`

are incomparable, and `p`

and `m`

are incomparable. By the transitivity of incomparability, `n`

and `m`

are incomparable, which contradicts the fact that `n <' m`

, so one of the preceding four cases applies.

The order of the input strings in the minimum output hence is determined up to permuting equivalent strings within an equivalence block. Since `m`

equivalent to `n`

implies that `mn = nm`

, we get the same output regardless of the permutation, and this output is thus minimum.

The interesting part of the correctness proof to me is proving that `<'`

is a strict weak ordering in the first place. In fact, it’s not unless we exclude the empty string, which wreaks havoc. For all nonempty strings `m`

, let `key(m)`

be the infinite string consisting of `m`

repeated infinitely often. To show that `<'`

is a strict weak ordering on nonempty strings, it suffices to show that `m <' n`

if and only if `key(m) < key(n)`

.

Suppose first that `m <' n`

. Then `mn < nm`

. Letting `|m|`

be the length of `m`

, we have `(m^|n|)(n^|m|) < (n^|m|)(m^|n|)`

by repeated application of the inequality `mn < nm`

. Since `|m^|n|| = |m||n| = |n^|m||`

, we conclude that `m^|n| < n^|m|`

and hence that `key(m) < key(n)`

.

Suppose now that `m <' n`

does not hold. If `nm < mn`

, then we argue as before that `key(n) < key(m)`

and hence that `key(m) < key(n)`

does not hold. Otherwise, `mn = nm`

. Since `(m^|n|)(n^|m|) = (n^|m|)(m^|n|)`

, we conclude that `m^|n| = n^|m|`

and thus that `key(m) = key(n)`

.

Similar Questions

To begin with I do not write code in java on a daily basis, though I am somewhat familar with most aspects. I have an integer array with mulitple values present. I then take this array and convert to

I would like to extract unique values from my (dynamically allocated) array. I have something like this : [0] 0 int [1] 1 int [2] 2 int [3] 2 int [4] 2 int [5] 5 int [6] 6 int [7] 6 int [8] 8 int [9]

How can we concat integers with integers varchar with varchar int with varchar in MySQL ?

I have one main array which is the returned data from a MySQL query for user table which looks like this : array(36) { [0]=> array(4) { [id]=> string(1) 101 [email]=> string(15) kkkk@g

How can we find a repeated number in array in O(n) time and O(1) complexity? eg array 2,1,4,3,3,10 output is 3 EDIT: I tried in following way. i found that if no is oddly repeated then we can achieve

How to find the nearest integer upon the provided one? Say, I have the following integers in the mysql database: 405, 600, 304. The question is how to I select 600 upon providing 550 or select 304 upo

I am stuck of something pretty basic. I need to take an array of integers and find if an integer n is divisible by the array of integers in a method called divisibleIntegers. The main method will prin

I need to find the minimum missing element from a sequence of non-negative integers. ex: I have: 0 5 10 4 3 1 The missing element is 2. In above sequence missing elements are 2 6 7 8 9 . The minimum

I trying to get the minimum values from the any column contains xx in the column name. Below is my code: <?php $array = array( array( 'id' => 1, '10xx' => 14, '11xx' => 32, '12xx' =>

How can you convert an image file (.png in this instance) into a 3d (one coordinate for width of image, one for weight and one for the integers showing Red, green and blue values) integer or byte arra

Q: I want to find minimum value in an array so far i have wrote the code with for loop, but i want to do this with threading concept, so how can i write the following code with multithreading? stati

Possible Duplicate: Find two missing numbers I been thinking for a while and can't seem to get an answer to this... So an array with n-2 unique integers in the range from 1 to n and O(1) space in ad

I need to extract 'thousands' from an integer (e.g. 1345 -> 1; 24378 -> 24) and since my application is going to do this a lot, I need to do this efficiently. Of course, division by 1000 is alwa

I've read and successfully tried the answer to How can I pass a Delphi string to a Prism DLL?, but wondered if it was possible to use a similar method to pass a Delphi array of integers (static or dyn

Given an Array A of N non negative integers, find an integer k, such that the sum of difference of each element with k is minimum. i.e. Summation(abs(A[i] - k)), 1 <= i <= N, or simply |A[1] - k

I've got an XML file storing an array of shorts in my resources. I need to assign this array, but Android API only provides a way to get array of ints (getResources.getIntArray()). I've ended up getti

I have an array $a = array( 2010-05-03 =>100, 2010-05-04 =>400, 2008-05-01 =>800, 2011-01-01 =>800 ); How do I find maximum and minimum by key( date)? For example: max => 20

I came across this question in a coding competition- You're given an array of positive integers and are allowed to change the sign of any of the integers whenever you require. Write a program to calcu

I use the following code to strip the product number from a page url so that i can query a database to check for a custom canonical link. $qs = explode('&',$_SERVER['QUERY_STRING']); $prodid = exp

I wrote the following class for generating random integers from a given interval [lower, upper]. class RandomInteger { protected: std::random_device randomDevice; std::default_random_engine randomEng

Given an unsorted integer array, and without making any assumptions on the numbers in the array: Is it possible to find two numbers whose difference is minimum in O(n) time? Edit: Difference between

This is an interesting question I had come across a while ago and had some trouble solving it. There's an unsorted integer array of size N stored with numbers 1,2..,N+M , with M integers missing from

I need to do a look up for an integer from a list of integers. I sort them and use the lower_bound to find the range the given integer falls in. This takes O(lgn). Is there any way I can do better tha

Given an array of integers (positive and negative), each having at most K bits (plus the sign bit), and it is known that the sum of all the integers in the array also has at most K bits (plus the sign

I am using below php functions to get highest and lowest integer value from my array. min($output[$k]) AND max($output[$k]) Problem: I want to get maximum and minimum integer values from that array ex

Given an array of integers, find the first integer that is unique. my solution: use std::map put integer (number as key, its index as value) to it one by one (O(n^2 lgn)), if have duplicate, remove th

I have a text file (Scanner file) with some integers and strings. I want to go through the file, take the integers and store them to an integer array (array1). Here is the method I am using: public v

int (*a)[5]; How can we Initialize a pointer to an array of 5 integers shown above. Is the below expression correct ? int (*a)[3]={11,2,3,5,6};

How can i find the minimum interval of an integer array in which all the unique elements of that array are present . For example my array is : 1 1 1 2 3 1 1 4 3 3 3 2 1 2 2 4 1 minimum interval is fro

In C++, we can define a custom locale that enables stream object to ignore non-digits in the file, and reads only the integers. Can we do something similar? How can we efficiently read only integers f

Is it possible to remove duplicate characters from a string without saving each character you've seen in an array and checking to see if new characters are already in that array? That seems highly ine

I have a linked list of objects each containing a 32-bit integer (and provably fewer than 232 such objects) and I want to efficiently choose an integer that's not present in the list, without using an

How to create a dynamic array of integers in C++ using the new keyword?

How can I efficiently assign a common initial value to a large array? For instance if I have a 100 by 100 by 100 integer array where all initial values should be zero. In matlab I would simply write:

Given an integer k and an sorted array A (can consist of both positive and negative numbers), output 2 integers from A such that a-b=k in O(n) time and O(1) space O(n logn) Solution: Traverse the arr

Given a list of integers, how can I best find an integer that is not in the list? The list can potentially be very large, and the integers might be large (i.e. BigIntegers, not just 32-bit ints). If i

How to efficiently convert a 32-bit integer into an array of four 8-bit integers in Python? Currently I have the following code, which is super slow: def convert(int32_val): bin = np.binary_repr(int

Can some one explain me how the internal behavior when we add two Integer objects in java? (like it is unbox Object into primitives and then add two integers and finally boxed it in to Integer object)

How can we judge the size of Integer Class Object ? for example : Integer i = new Integer(10); so in the above case what is the size of 'i'. Does it valid ??

I am writing a simple big integer library for exercise. I would like to use it in a simple implementation of RSA. I have read all the previous threads but I have not found an answer to my question. I

For instance I have a model like so: class Record(models.Model): name = CharField(...) price = IntegerField(...) year = IntegerField(...) How can I find the minimum or maximum of year without using a

I am making application using c#. I have one queue as follows... Queue QueueData = new Queue(60); I want to find the min and max element from that queue. Any ideas?

I found this question on an online forum: Really interested on how it can be solved: Given an array A of positive integers. Convert it to a sorted array with minimum cost. The only valid operation are

I having a problem with coding this: Write a static method named removeDuplicates that takes as input an array of integers and returns as a result a new array of integers with all duplicates removed.

As part of my CS course I've been given some functions to use. One of these functions takes a pointer to unsigned chars to write some data to a file (I have to use this function, so I can't just make

This question already has an answer here: How to convert List<Integer> to int[] in Java? 11 answers Is there a way, to convert a List of Integers to Array of ints (not integer). Something

I'm having trouble figuring out how exactly to make it find the max number and minimum number in the array. Write a method range that accepts an ArrayList of integers as a parameter and that returns t

I was asked to implement an algorithm that takes as input the following: -A sorted array of integers a, for example a=[0,0,0,0,0,2,4,4,4,4,4]. If it helps the actual input is given as two arrays from

I have a PHP array like this one: array( [0] => 1 [1] => 2 [2] => 3 [3] => Some strings ) How can I remove an entry that is not an integer number from an array? I need to output this: arr

I am new to Java development, developing an android application. I have an array of integer. I am looking for solution to pick number randomly from this integer array. for example I have an array new