CareerCup

Sort the array. The largest numbers should be in the least significant positions, so build up your two integers by alternating from the two arrays.
E.g. 1 3 5 7 8 9 => 1 and 3, then 15 and 37, then 158 and 379. 0 is a special case, if not allowed to use that as a leading digit then have to use it as the second digit.

My approach was to create two vectors with alternate elements after sorting the original vector in O(nlogn) time complexity. Then sum each vector's digit. Written in C++.

Output:

207

Code:

#include <iostream>
#include <vector>
#include <algorithm>

int calculate_min_sum(std::vector<int>& vec) {
	std::vector<int> vec_a;
	std::vector<int> vec_b;

	// Sort the vector
	std::sort(vec.begin(), vec.end());
	
	// Create two vectors with alternate elements
	for (size_t i = 0; i < vec.size(); i++) {
		if (i % 2 == 0)
			vec_a.push_back(vec[i]);
		else
			vec_b.push_back(vec[i]);
	}

	// Convert vectors  to numbers
	int vec_a_val = 0;
	for (size_t i = 0; i < vec_a.size(); i++) {
		vec_a_val = vec_a_val * 10 + vec_a[i];
	}
	
	int vec_b_val = 0;
	for (size_t i = 0; i < vec_b.size(); i++) {
		vec_b_val = vec_b_val * 10 + vec_b[i];
	}

	// Return sum
	return vec_a_val + vec_b_val;
}

int main() {
	std::vector<int> vec{7, 9, 1, 8, 2};
	std::cout << calculate_min_sum(vec) << std::endl;
}

To make sum minimum, both of its operands should also be minimum. For given set of digits, a number will be minimum when smallest unused digit appears at higher positional value. Having sorted array of digits makes it easy, just give next available smallest number to higher position to each number. Code is as follows -

/* 
  sum will be least when both operands are least
  for given "sorted" array of digits operands will be least
  when small digits will take higher positions and big digits
  take lower positions
  distribute uniformly small and big digits among two operands
*/
int min_sum(int a[], int n)
{
  int number1 = 0;
  int number2 = 0;
  int i;

  for(i=0; i<n; i++)
  {
    if( i%2 )
      number1 = (10*number1 + a[i] );
    else
      number2 = (10*number2 + a[i] );
  } 
  printf("\n%d %d", number1, number2);
  return number1+number2;
}

int main(int argc, char *argv[])
{
  int a[] = {1,2,7,8,9};
  int n   = sizeof(a)/sizeof(a[0]);
  printf("\n%d\n",min_sum(a,n));
  return 0;
}

public void findMinSum(int[] x){
		Arrays.sort(x);
		String first = "";
		String second = "";
		for(int i=0,l=x.length; i<l; ++i){
			if(i%2==0){
				first+=x[i];
			}else{
				second+=x[i];
			}
		}
		int num1 = Integer.parseInt(first);
		int num2 = Integer.parseInt(second);
		System.out.println("Numbers are : " + first + " and " + second);
		System.out.println("Sum is : " + (num1+num2));
	}

/**
 * Programming Language Used : PHP
 * 
 * This method would return the two numbers which form the minimum sum.
 * 
 * @author Varun Jalandery <varun.jalandery@gmail.com>
 * 
 * @param array of numbers
 * @return array of two numbers which form the minimum sum
 */
function getTwoMinimumSumFormingIntegers($array)
{
    $numberOne = '';
    $numberTwo = '';

    sort($array); //sorting the array in ascending order

    $i = 0;
    while (isset($array[$i])) {
        $numberOne .= $array[$i++];
        $numberTwo .= $array[$i++];
    }
    
    return array(
        0 => (int) $numberOne,
        1 => (int) $numberTwo,
    );

}

This is some thing that looks easy but very tough when u check with all possible values. I have got the answer finally..

public class CupTest {

	public static void main(String args[])
	{
		System.out.println(" Enter any number ");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String number = br.readLine();
			int firstHalf;
			int secondHalf;
			
			int[] intArray = new int[number.length()];
			int i;
			for(i = 0; i < number.length();i++)
				intArray[i] = Integer.parseInt(number.substring(i, i+1));
			
			if(number.length() % 2 == 0)
			{
				firstHalf = Integer.parseInt(number.substring(0,(number.length()/2)));
				secondHalf = Integer.parseInt(number.substring(number.length()/2, number.length()));
				System.out.println("Minimum Count is " + (firstHalf + secondHalf));
			}
			else{
				String side = null;
				int j;
				for(i= 0, j = (number.length()/2); j < number.length() -1 ; i++,j++)
				{
					firstHalf = Integer.parseInt(number.substring(i,j - i));
					System.out.println("first half " + firstHalf);
					
					secondHalf = Integer.parseInt(number.substring((j+1), number.length()));
					System.out.println("Second half " + secondHalf);
					
					if(firstHalf > secondHalf)
					{
						System.out.println("Broken to second Half" + firstHalf + secondHalf );
						side = "left";
						break;
					}else if(firstHalf < secondHalf)
					{
						System.out.println("Broken to first left" + firstHalf + secondHalf );
						side = "right";
						break;
					}
				}
				
				if(side == null)
				{
					// Means values on both the sides are equal for the given Array
					/*if(Integer.parseInt(number.substring(i,j)) < Integer.parseInt(number.substring(j+1, number.length())))
					{
						left = true;
						break;
					}else if(Integer.parseInt(number.substring(i,j)) > Integer.parseInt(number.substring(j+1, number.length())))
					{
						left = false;
						break;
					}*/
					for(i= 0, j = (number.length()/2); j < number.length() -1 ; i++,j++){
					if(intArray[i] < intArray[j])
					{
						side = "left";
						break;
					}else if(intArray[i] > intArray[j])
					{
						side = "right";
						break;
					}
					}
				}
				if(side.equalsIgnoreCase("left"))
					System.out.println(" Minimum Count is " + (Integer.parseInt(number.substring(0,(number.length()/2)+1)) + Integer.parseInt(number.substring((number.length()/2+1),number.length()))));
				else
					System.out.println(" Second is minimum its Count is " + (Integer.parseInt(number.substring(0,number.length()/2)) + Integer.parseInt(number.substring(number.length()/2,number.length()))) );
			}
			
			
		} catch (NumberFormatException | IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		
	}
}

algo would be like this:
1. Sort array O(nlogn)
2. Divide the array in two parts and add that two parts , if length of array is not even then take even no. of elements in first part and odd number of elements in second part and then add them up. - O(n)
2.a If array contain 0(zero) then take starting point of array from non zero element.

So total complexity would be O(nlogn) + O(n) = O(nlogn)
Please let me know if there is an negative test case.

1. Sort the numbers using a linear sort (O(n))
2. int x=0, y=0
3. While(i < n) {
if(i%2 == 0) {
x *= 10 + a[i];
} else {
y *= 10 + a[i];
}
}
min_sum = x + y;

Since the sum has to be minimum, implies
1) both the numbers are supposed to in ascending order
2) length of both the numbers should be half the length of array.
3) The minimum number in the array has to be the as the starting(first) number of either of the two numbers to be found.
assume 1,2,7,8,9 - then 1 has to be first number in either of the two numbers to be found (127).

Steps
a) sort the array in ascending order.
b) Take the first element of the array (minimum in the array) as the starting of either of the numbers to be found.
c) Now first element of a number to be found is fixed. Have a global variable min initialized to a high value.
d) As in the example you have to choose numbers among 2,7,8,9 and in (b) we chose 1 as a part of a number to be found.
e) Now as for the (2) point one number will be of length 3, another will be of length 2.
f) Get 2 numbers from the array left 2,7,8,9 to be grouped with 1 (already choosen). for instance 27 89, remember both the numbers here should be in ascending order (1). No of ways to choose two numbers here are 6 [4!/(2!*2!)].
g) Now we can have 127 and 89 or 189 or 27 sum and compare both, next 28 is chosen another will be 79 again do sum and comparision, In short this logic is exactly same as Subset sum problem (Dynamic Programming) logic, with a slight modification. Using recursion you can find the two numbers from the array 2,7,8,9 associate each of them with 1 and check whether it's minimum.
h) For handling zeros in the array, after the sort neglect all the zeros and start the work with the fresh array with no zeros.
2,7,8,9

27,89 => 127,89 or 27,189
28,79 => 128,79 or 179,28
29,78 => 129,78 or 178,29

Hence the six combinations.

Assuming all the number are position (including zero)
1) Sort the array in ascending order
2) Ignore all the leading zeros and assume that list starts from the first non-zero number
3) For all non-zero numbers, make number at position 1 first digit of first number and number at position 2 first digit of second number. Make number at position 3 the second digit of first number ans number at position 4 the second digit of second number and keep going like this until the end of list reached.
Example: sorted list: 1 2 3 4 5 6
First Number: 1
Second Number: 2
First Number: 13
Second Number: 24
First Number:135
Second Number 246
Solution 135 + 246 = 381

Python code:

a = [1, 2, 7, 8, 9]
a.sort()

n1=n2=''

for i in range(0, len(a)):
if i % 2 == 0:
n1 = n1 + str(a[i])
else:
n2 = n2 + str(a[i])

print 'First number: %s'%n1
print 'Second number: %s'%n2

Python code:

a = [1, 2, 7, 8, 9]
a.sort()

n1=n2=''

for i in range(0, len(a)):
if i % 2 == 0:
n1 = n1 + str(a[i])
else:
n2 = n2 + str(a[i])

print 'First number: %s'%n1
print 'Second number: %s'%n2

Three questions:
Can highest magnitude digits be 0?
Is the array size constrained?
Can digits be duplicated in the array?

Here my solution in C++... you all should handle different length for a and b giving the min sum:

int get_front_rm_front(std::vector<int> &vec, int &ten_unit) {
int r = vec.front() * ten_unit;
ten_unit /= 10;
vec.erase(vec.begin());
return r;
}

std::pair<int,int> find_min_sum(std::vector<int> &vec) {
int len_first = (vec.size() / 2) + vec.size() % 2;
int len_second = vec.size() / 2;
int first_ten_unit = pow(10, len_first-1);
int second_ten_unit = pow(10, len_second-1);
int first = 0;
int second = 0;

if(vec.size() < 2) {
return std::pair<int,int>(0,0);
}

std::sort(vec.begin(), vec.end());

if(len_first > len_second) {
first += get_front_rm_front(vec, first_ten_unit);
}

while(vec.size() > 1) {
if(first > second) {
first += get_front_rm_front(vec, first_ten_unit);
second += get_front_rm_front(vec, second_ten_unit);
}
else {
second += get_front_rm_front(vec, second_ten_unit);
first += get_front_rm_front(vec, first_ten_unit);
}
}

return std::pair<int,int>(first,second);
}

import java.util.Arrays;


public class Minimum {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int arr[]={1,2,7,8,9};
        
        Arrays.sort(arr);
                
        int mid=arr.length/2;
        int remainder=arr.length%2;
        int power=mid;
        int sum=0;
        int count=0;
        if(remainder==1)
        {
        	sum+=arr[0]*Math.pow(10, power);
        	//System.out.println(sum);
        	power--;
        	for(int i=1;i<arr.length;i++)
        	{
        		count++;
        		
        		sum+=arr[i]*Math.pow(10, power);
        		if(count==2)
        		{
        			power--;
        			count=0;
        		}
        	}
        	
        }
        else if(remainder==0)
        {power--;
        	for(int i=0;i<arr.length;i++)
        	{
        		count++;
        		sum+=arr[i]*Math.pow(10, power);
        		if(count==2)
        		{
        			power--;
        			count=0;
        		}
        	}
        }
        System.out.println(sum);
	}

}

After sorting the array:
Basically there are two cases:
1) If the number of digits are even:
first two digits are multiplied with 10^(mid-1) each and added
second two digits are multiplied with 10^(mid -2) each and added and so on..
2)odd:
first digit is multiplied with 10^mid.. and so on as in 1 above
The theory is digit at highest place value should be least for both numbers..

private int minSum(int[] a) {
	//checks on null
	if(a == null || a.length == 0) {
		return -1;
	}
	int length = a.length;
	if(length == 1) {
		return a[0];
	}

	Array.sort(a);
	int nonZeroInd = getNonZeroInd(a);

	if(nonZeroInd == length - 1) {
		return  getOneNonZeroSum(a);
	}

	if(nonZeroInd > 0) {
		swapZeros(a, nonZeroInd);
	}

	return getSum(a);
}

private int getSum(int[] a) {
int sum1 = 0;
	int sum2 = 0;

	for(int i = 0; i < length; i++) {
		if(i % 2 == 0) {
			sum1 = sum1 *10 + a[i];
		} else {
			sum2 = sum2 * 10 + a[i];
		}
	}
	return sum1 + sum2;

}

private void getNonZeroInd(int[] a) {
	int len = a.length;
	int nonZeroIndex = 0;
	for(int i = 0; i < length; i++) {
		if(a[i] != 0) {
nonZeroIndex = i;
break;
		}
	}
	return nonZeroIndex;
}

private int getOneNonZeroSum(int[] a) {
	int len = a.length;
	int sum = a[len - 1];
	int zeros = Math.pow(10, len - 2);
	return sum * zeros;
}

private void swapZeros(int[] a, int nonZeroInd) {
	int len = a.length;
	swap(a, 0, nonZeroInd);
	swap(a, 1, nonZeroInd + 1);
}

private void swap(int[] a, int i, int j) {
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_SIZE 10

void sort_arr(int arr[], size_t aSize)
{
int i, j, temp;

for ( i = 0; i < aSize - 1; i++)
{
for (j = i + 1 ; j < aSize ; j++)
{
if ( arr [ i ] > arr[j ] )
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}


int make_min_sum(int arr[], int size)
{
int i=0;
int num1=0, num2=0, temp;

while ( i < size )
{
while ( i <= size /2)
{
if ( i == size / 2)
{
num1 = num1 + arr[size -1];
num1 = num1 * 10;
temp = i++;
break;
}
num1 = num1 + arr[i];
num1 = num1 * 10;
i++;
}

if ( i == size -1)
{
num2 = num2 + arr[temp];
num2 = num2 * 10;
break;
}

num2 = num2 + arr[temp];
temp = i;
num2 = num2 * 10;
i++;
}

return (num1 + num2) / 10;
}

int main(int argc, char **argv)
{

int arr[MAX_SIZE];
char str[3];
int sum, size = 0;
int i, i_val, num;

printf("Enter number");
gets(str);
num = atoi(str);

while (num != 0)
{
i_val = num % 10;
arr[size++] = i_val;
num = num /10;
}

sort_arr(arr, size);

printf("arr elements are after sort:\n");
for ( i = 0; i < size; i++)
printf("%d", arr[i]);

sum = make_min_sum(arr, size);

printf("min sum :%d\n", sum);

return 0;
}

1) Arrange the elements in array in ascending order
2) make two sub arrays with half of the length each ( if total digits are 6, one with 3 and other with 3 and if total is 5 one with 3 and other with 2).
3) Now lowest element to first array and then next lowest to second and so on.
4) Logic is simple, we should have lowest values in most significant bit.

Below program is in java. I just written so casually. but it gives the solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class GoogleQuestion {
	
	public static void main(String[] args) throws IOException
	{
		System.out.println(" Enter the list of Integers ");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input = br.readLine();
		int a[] = new int[input.length()];
		int i = 0;
		for(i =0; i < input.length();i++ )
		{
			a[i] = Integer.parseInt(input.substring(i, i+1));
		}
		
		ArrayList<Integer> al = new ArrayList<Integer>();
		for(i = 0 ; i < input.length() ; i ++)
			al.add(a[i]);
		
		int sub1[];
		int sub2[];
		
		if((input.length())  % 2 == 0)
		{
			sub1 = new int[input.length()/2];
			sub2 = new int[input.length()/2];
		}else
		{
			sub1 = new int[(input.length()/2)+1];
			sub2 = new int[input.length()/2];
		}
		
		Collections.sort(al);;
		i = 0;
		for(Integer k:al)
		{
			a[i++] = k;
		}
		
		int j;
		
		for(i = 0,j = 0 ; i < input.length();i++,j++)
		{
			sub1[j] = a[i];
			i++;
			
			if( i < input.length())
				sub2[j] = a[i];
			
		}
		
		int x=0,y = 0;
		
		for(i=0;i<sub1.length;i++)
		{
			x = x*10 + sub1[i];
		}
		
		for(i=0;i<sub2.length;i++)
		{
			y = y*10 + sub2[i];
		}
		
		System.out.println(" Sub1 is " + x);
		System.out.println(" Sub2 is " + y);
		
		System.out.println( " Minimum total of the Sub Arrays is " + (x+y));
		
	}

}

1.  If Array Length < 2 return 0 //invalid case
2.  Sort the array
3.  Let num1 and num2 be the two required numbers.
4.  startingIndex = 2 => To adjust for the case where the array may have odd number of elements, 
		process first two OR three elements as a special case.

5.  if array length is odd:-
	// process first three elements
	5.a num1 = array[0]*10 + array[1];
	5.b num2 = array[2];
	5.c startingIndex ++;
	

6.  else
	// process first two elements
	6.a num1 = array[0]
	6.b num2 = array[1]

7. Now the remaining array is of even length, process next two elements at a time, adding first element to num1 and second to num2.
	 for(int i = startingIndex;i<array.length;i+=2)
	 {
	 	num1 = num1*10 + array[i];
		num2 = num2*10 + array[i+1];
	 }
8. Result = num1 + num2;

-----------------------------------------------------------------------------------
Example : - {1,2,7,8,9}
1. Considering first three elements, num1 = 12 , num2 = 7, RemainingArray = {8,9}
2. num2 = 128, num3 = 79

Example :- {0,0,0,6,7}
1. Considering first three elements, num1= 0, num2 = 0, Remaining = {6,7}
2. num1 = 6, num2 = 7

Example :- {9,2,7,5,7,2,1,5,4,6} 

1. Sorted Array = {1,2,2,4,5,5,6,7,7,9}
2. Considering first two elements - num1 = 1, num2 = 2, Remaining = {2,4,5,5,6,7,7,9}
3. num1 = 12, num2 = 24 , Remaining = {5,5,6,7,7,9}
4. num1 = 125, num2 = 245 , Remaining = {6,7,7,9}
5. num1 = 1256, num2 = 2457, Remaining = {7,9}
6. num1 = 12567, num2 = 24579

Here's my attempt, done in Java.

import java.util.*;

/*
Given the array of digits (0 is also allowed), what is the minimal sum of two integers that are made of the digits contained in the array?
For example, array: 1 2 7 8 9. The min sum (129 + 78) should be 207
*/

public class minSum
{
   public static void main(String[] args)
   {
      int[] arr = {1, 2, 7, 8, 9, 0};
      System.out.println(findMinSum(arr));
   }
   public static int findMinSum(int[] arr)
   {
      Arrays.sort(arr);
      String one = "";
      String two = "";
      for(int k = arr.length-1; k >= 0; k-=2)
      {
         one = arr[k] + one;
         if(k != 0)
            two = arr[k-1] + two;
      }
      if(one.substring(0, 1).equals("0"))
         one = one.substring(1, 2) + "0" + one.substring(2);
      if(two.substring(0, 1).equals("0"))
         two = two.substring(1, 2) + "0" + two.substring(2);
      return Integer.parseInt(one) + Integer.parseInt(two);
   }

}

Output:

387

int minSum(vector<int>& v) {

	sort(v.begin(), v.end());
	int a[2] = {0};

	for (int i = 0; i < v.size(); ++i) {
		a[i%2] = (a[i%2]*10)+v[i];
	}

	return a[0] + a[1];
}

only sum is asked no need to generate both the numbers

int min_sum(int a[],int size)
{
	int sum=0;
	sort(&a[0],&a[size]);
	if(size%2==1)
		sum+=a[0];
	for(int i=size%2;i<size;i+=2)
		sum = (sum*10+a[i]+a[i+1]);
	return sum;
}

just generate the sum;

instead of starting from the start of the sorted array we can try from end
please find the algo

1) sort the array
2)two numbers A,B(initialize to 0)
3)A=last element of array
4)i=last-1
5)if(i<0) return (A+B)
6)if(A<B) go to 7 else goto 8
7)A=pow(10,lengthof(A)) + array[i], goto 9
8)B=pow(10, lenghtof(B)) + array[i]
9)i--; goto 5.

I found a simple solution
Array : {1 2 7 8 9}
Assumption : Array is sorted

Output : need to construct the 2numbers from array numbers such that sum is min

Solution :

1)num1=num2=0
2)mul1=mul2=1
3)for(int i=0;i<arr.len;i++)
{
if(i%2 = 0 && arr[i] !=0)
{
num1=arr[i]*mul1 ;
mul1*=10;
}
else if(arr[i]!=0)
{
num2=arr[i]*mul2;
mul2*=10;
}
}
4)Print num1 and num2
5) So min sum is num1+num2

def mini_sum(A):
    n = len(A)
    if n == 0:
        return 0
    A.sort()
    if n % 2 == 1:
        total = A[0]
        start = 1
    else:
        total = 0
        start = 0
    for i in xrange(start, n, 2):
        total = total * 10 + A[i] + A[i+1]
    return total

A = [1, 2, 7, 8, 9]
print(mini_sum(A))

- Remove the zeros
- Sort the the digits
- First number will be number formed with digits with even indices
- Second number will be number formed with digits with odd indices

For example, if input is 845101420023

When the zeroes are remove it becomes 845114223
When it is sorted it becomes 112234458
First number: 12348
Second number: 1245

Suppose this array is sorted. coding as below.
#include <stdio.h>

#define ARRAY_NULL 1
int main(int argc, char **argv){
if(array = NULL){
return ARRAY_NULL;
}
int first_int = 0;
int second_int = 0;
int length;

length = sizeof(array);
for(int i = 0; i < length; i++){
if(i % 2){
first_int = first_int * 10 + array[i];
}
else{
second_int = second_int * 10 + array[i];
}
}
printf("The least sum number is : %d = %d + %d\n", first_int+second_int, first_int, second_int);
return 0;
}

Suppose this array is sorted. coding as below.
#include <stdio.h>

#define ARRAY_NULL 1
int main(int argc, char **argv){
if(array = NULL){
return ARRAY_NULL;
}
int first_int = 0;
int second_int = 0;
int length;

length = sizeof(array);
for(int i = 0; i < length; i++){
if(i % 2){
first_int = first_int * 10 + array[i];
}
else{
second_int = second_int * 10 + array[i];
}
}
printf("The least sum number is : %d = %d + %d\n", first_int+second_int, first_int, second_int);
return 0;
}

If this array not be sorted, we will sort it first.

1. Sort the array.
2. Use two temporary number for the two integer. Append the next digit to them in turn.
3. Use a temporary variable to remember the leading 0s. When the first non-zero digit is found, add it to the head.

public class Solution {
    public static int getMinSum(int[] arr) {
        // sort the array
        Arrays.sort(arr);

        int num1 = 0, num2 = 0;
        int leading1 = 1, leading2 = 1;

        for (int i=0; i < arr.length; i++) {
            int x = arr[i];
            
            // append the digit to the first number
            if (num1 == 0) {
                if (x == 0) {   // leading zero
                    leading1 *= 10;
                } else {
                    num1 = x * leading1;
                }
            } else {
                num1 = num1 * 10 + x;
            }

            // append the digit to the second number
            i++;
            if (i < arr.length) {
                x = arr[i];

                if (num2 == 0) {
                    if (x == 0) {
                        leading2 *= 10;
                    } else {
                        num2 = x * leading2;
                    }
                } else {
                    num2 = num2 * 10 + x;
                }
            }
        }

        return num1 + num2;
    }
}

public static int findMinimum(int[] arr) {
Arrays.sort(arr);
int i = 0;
while (arr[i] == 0) {
i++;
}
if (arr.length - i < 2) {
return -1;
}
swap(arr, 0, i);
swap(arr, 1, i + 1);
int value = 0;
int start = 0;
if (arr.length % 2 == 1) {
value = arr[0];
start++;
}
for (int k = start; k < arr.length; k += 2) {
value = 10 * value + arr[k] + arr[k + 1];
}
return value;
}

private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int min_sum(int *a, int len)
{
int size= len-1, flag=0;
int unit1=0,unit2=0,tens1=0,tens2=0,hundreds1=0,hundreds2=0;
int thousands1=0,thousands2=0,tenthousands1=0,tenthousands2=0;
int num1=0,num2=0;

cout << "Total number of elements in array =" << len << "\n";

unit1=a[size]; size--;
//cout << size;
unit2=a[size]; size--;
//cout << size;

if (size>=0)
{
tens1=a[size];
size--;
}

if (size>=0)
{
tens2=a[size];
size--;
}


if (size>=0)
hundreds1=a[size]; size--;

if (size>=0)
hundreds2=a[size--];

if (size>=0)
thousands1=a[size--];

if (size>=0)
thousands2=a[size--];

if (size>=0)
tenthousands1=a[size--];

if (size>=0)
tenthousands2=a[size--];


num1 = unit1 + tens1 * 10 + hundreds1 * 100 + thousands1 * 1000 + tenthousands1 * 10000;
num2 = unit2 + tens2 * 10 + hundreds2 * 100 + thousands2 * 1000 + tenthousands2 * 10000;

for (int i=0;i<len;i++)
{
if (a[i]==0)
flag++;
}

int t1=num1,t2=num2;

while(t1)
{
t1=t1/10;
cout << "\n t1=" << t1;
}

if(flag--)
num2=num2 * 10;
if(flag--)
num1=num1 * 10;

cout << "The two numbers which form min sum are:\n" << num1 << "\t" << num2 << "\n";
cout << "Minimum sum required = " << num1+num2 << "\n";

return 1;

}

int sort_it (int *a, int len)
{

int i,j,temp;
for (i=0;i<len;i++)
{
for (j=0;j<len-1-i;j++)
{
if (a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}

cout<< "\n{\t";

for (int i=0; i<len; i++)
{
cout << a[i]<< "\t";
}

cout<< "\t}\n";
}

int main()
{
int array[]= {1,9,0,2};
//{9,2,7,5,7,2,1,5,4,6};
//{1,3,5,3};
//{1,2,7,8,9};
//{ 2,7,6,5,3,4,8,9,1};

int len= sizeof(array)/sizeof(array[0]);


cout<< "{\t";

for (int i=0; i<len; i++)
{
cout << array[i]<< "\t";
}

cout<< "\t}";

sort_it(array,len);
min_sum(array,len);

return 0;
}

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int min_sum(int *a, int len)
{
    int size= len-1, flag=0;
    int unit1=0,unit2=0,tens1=0,tens2=0,hundreds1=0,hundreds2=0;
    int thousands1=0,thousands2=0,tenthousands1=0,tenthousands2=0;
    int num1=0,num2=0;

    cout << "Total number of elements in array =" << len << "\n";

        unit1=a[size]; size--;
        //cout << size;
        unit2=a[size]; size--;
        //cout << size;

    if (size>=0)
    {
        tens1=a[size];
        size--;
     }

    if (size>=0)
    {
        tens2=a[size];
        size--;
       }


    if (size>=0)
        hundreds1=a[size]; size--;

    if (size>=0)
        hundreds2=a[size--];

    if (size>=0)
        thousands1=a[size--];

    if (size>=0)
        thousands2=a[size--];

    if (size>=0)
        tenthousands1=a[size--];

    if (size>=0)
        tenthousands2=a[size--];


    num1 = unit1 + tens1 * 10 + hundreds1 * 100 + thousands1 * 1000 + tenthousands1 * 10000;
    num2 = unit2 + tens2 * 10 + hundreds2 * 100 + thousands2 * 1000 + tenthousands2 * 10000;

    for (int i=0;i<len;i++)
    {
        if (a[i]==0)
            flag++;
    }

int t1=num1,t2=num2;

while(t1)
{
    t1=t1/10;
    cout << "\n t1=" << t1;
}

    if(flag--)
        num2=num2 * 10;
    if(flag--)
        num1=num1 * 10;

    cout << "The two numbers which form min sum are:\n" << num1 << "\t" << num2 << "\n";
    cout << "Minimum sum required = " << num1+num2 << "\n";

    return 1;

}

int sort_it (int *a, int len)
{

    int i,j,temp;
    for (i=0;i<len;i++)
    {
        for (j=0;j<len-1-i;j++)
        {
            if (a[j]>a[j+1])
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }

    cout<< "\n{\t";

    for (int i=0; i<len; i++)
    {
      cout << a[i]<< "\t";
    }

    cout<< "\t}\n";
}

int main()
{
    int array[]= {1,9,0,2};
    //{9,2,7,5,7,2,1,5,4,6};
    //{1,3,5,3};
    //{1,2,7,8,9};
    //{ 2,7,6,5,3,4,8,9,1};
   
    int len= sizeof(array)/sizeof(array[0]);


    cout<< "{\t";

    for (int i=0; i<len; i++)
    {
      cout << array[i]<< "\t";
    }

    cout<< "\t}";

    sort_it(array,len);
    min_sum(array,len);

    return 0;
}

Slightly different approach than much of what has already been posted.

1) Assume that the list is sorted
2) Note that when we do our sum, digits in the same position can exist in either number and provide the same result: eg, 145 + 39 vs 135 + 49. This solution provides only the sum, not the list of possible ways to get there.
3) backtrack through the numbers to put digits in their right spots right away

#include <iostream>

int minsum(int* nums, int count)
{
	//assume sorted

	int num_a=0, num_b=0, round=1;

	for (int i = count-1; i>=0; --i)
	{
		num_a += nums[i] * round; 
		if (i>0) num_b += nums[--i] * round;
		round *= 10;
	}

	return num_a + num_b;
}


int main()
{
	int testarray[5] = {1,2,7,8,9};
	std::cout << minsum(testarray,5) << std::endl;
	return 0;
}

If we assume that numbers starting with 0 (like 017) are invalid, that doesn't mean we should throw out all zeros, as someone previously stated. We could still have 107. In this case after you do your initial sort you should move the zeros so they start at the 3rd index, and move the first 2 integers after the zeros the the first two index. You can check out the Matlab code at my blog meditationsofmarcus.blogspot.com. I'll also include it here. I didn't try to make it very clean:

function [S]=minsum(V)
% Returns the minimum sum of 2 integers using all of the digits in vector V
% ex. 12789 =179+28=207

if sum(V~=0)<2
    display('function cannot compute minimun sum if there are not at least 2 integers')
    return
end


v=sort(V)
L=numel(V);
n=sum(v==0);

if n~=0
    vnew(1:2)=v(n+1:n+2);
    vnew(3:(n+2))=0;
    vnew(n+3:L)=v(n+3:end);
    v=vnew
end
    

v1=v(1:2:end)
v2=v(2:2:end)
num1=0;
num2=0;




if mod(L,2)==0
   
    for i=1:L/2
        num1=num1+v1(i)*10^(L/2-i);
        num2=num2+v2(i)*10^(L/2-i);
    end
else
    for i=1:(L+1)/2
         num1=num1+v1(i)*10^((L+1)/2-i);
    end
   
    for j=1:(L-1)/2
        num2=num2+v2(j)*10^((L-1)/2-j);
    end
end
num1
num2
S=num1+num2



end

Firstly, the elements in the array can belong to a finite set {0-9}. So, instead of sorting the array, just a class that can handle such frequency distribution will do. Creation of an instance and population of data will take place in linear time
Secondly, allowing 0 in the input array makes sense only if leading zeros were not allowed, otherwise, a linear time pre-processing can get rid of all the zeros. So, I have made a separate function to handle such a case which is invoked only if leading zeros are not allowed

Input format :
t //number of test cases
{//each test case
n//number of elements in array
za//=1 if leading zeros are not allowedother wise !=1
<ai> ith element of array
}
test cases that I have tested upon :
6
5 0
1 2 7 8 9
5 1
0 2 7 8 9
5 1
1 8 2 9 7
5 1
0 0 0 6 7
5 0
0 0 0 6 7
10 1
9 2 7 5 7 2 1 5 4 6
Expected output:
207//as given
287//208+79 : leading zero not allowed
207//just another permutation of given test case
670//600+70 : leading zero not allowed
13//006+07 : leading zero allowed
37146//12567+ 24579

Code :

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
bool debug=false;
class Set{
	vector<int> freq;
	int maxDigit,swapDigit,swap;
	bool zero_allowed;
	void manage_zero(){
		if(debug)cout<<"max digit : "<<maxDigit<<endl;
		if(zero_allowed){
			int sum_freq=0;
			for(int i=1;i<10;++i)sum_freq+=freq[i];
			if(swap==0 && sum_freq==2 && freq[0]!=0){
				if(debug)cout<<"Swapping in 0 from "<<maxDigit<<endl;
				swap=1;
				swapDigit=maxDigit;
				maxDigit=0;
			}
			if(swap==1 && freq[0]==0){
				if(debug)cout<<"Swapping back "<<swapDigit<<endl;
				maxDigit=swapDigit;
				swap=2;
			}
		}
	}
public:
	Set(int n,bool za):
	freq(vector<int>(10,0)),
	maxDigit(9),
	zero_allowed(za),
	swap(0){
		int num;
		while(n--){
			scanf("%d",&num);
			++freq[num];
		}
		while(maxDigit>=0 && freq[maxDigit]==0)--maxDigit;
	}
	int getMax(){
		while(maxDigit>=0 && freq[maxDigit]==0)--maxDigit;
		manage_zero();
		if(maxDigit==-1){
			if(debug)cout<<"Returning due to empty set"<<endl;
			return -1;
		}
		--freq[maxDigit];if(debug)cout<<"freq["<<maxDigit<<"] being reduced to "<<freq[maxDigit]<<endl;
		return maxDigit;
	}
	bool isEmpty(){
		while(maxDigit>=0 && freq[maxDigit]==0)--maxDigit;
		manage_zero();
		if(maxDigit==-1){
			if(debug)cout<<"Returning due to empty set"<<endl;
			return true;
		}
		return false;
	}
};
int main(int argc , char **argv)
{
	if(argc>1 && strcmp(argv[1],"DEBUG")==0) debug=true;
	int t,n,za;scanf("%d",&t);
	long long int sum,place_value;
	while(t--){
		scanf("%d %d",&n,&za);
		Set s(n,za==1);
		place_value=1;
		sum=0;
		while(!s.isEmpty()){
			sum+=s.getMax()*place_value;if(debug)cout<<sum<<endl;
			if(s.isEmpty())break;
			sum+=s.getMax()*place_value;if(debug)cout<<sum<<endl;
			place_value*=10;
		}
		printf("%lld\n",sum);
	}
	return 0;
}

/**
 * Programming Languguage Used : Java
 * 
 * This method will print the two numbers which form the minimum sum.
 * 
 * @author Vincent Sam <kobesam@gmail.com>
 * 
 * @param array of numbers
 * @return void (prints the two numbers which form the minimum sum).
 * 
 */
public static void getMininalSum(int[] digits) {
	int minSum = 0, i = 0;
	int len = digits.length;
	StringBuilder op1 = new StringBuilder(), op2 = new StringBuilder();
		
	Arrays.sort(digits);
	while (i < len) {
		if (i%2==0)  	op1.append(digits[i++]);
		else			op2.append(digits[i++]);
	}
	minSum = (len > 0) ? Integer.parseInt(op1.toString()) + Integer.parseInt(op2.toString()) : 0;
	System.out.printf(" The minimal sum of %s, %s = %d \n", op1.toString(), op2.toString(), minSum);	
}

int[] a = { 1, 2, 7, 8, 9 };
		
		Arrays.sort(a);

		int x = 1;
		int i = a.length - 1;
		int sum = 0;
		while (i >= 1) {
			int digit1 = a[i--];
			int digit2 = a[i--];
			sum += digit1*x +digit2*x;
			x*=10;
		}
		
		sum+= a[0]*x;
		
		System.out.println(sum);

Sort the array. Then take the larger digits higher then zero. Then insert zeros in a way that that satisfies the requirement.

Sorting in the code is done using a library function, but it can be achieved in O(n) using counting sort. The remaining code is O(n), so its O(n) overall...

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;

public class GetSumFromDigitArray {
	public static int getMinSum(int  [] digits){
		int n = digits.length;
		if( n == 0) return 0;

		Arrays.sort(digits);
		LinkedList<Integer> n1 = new LinkedList<>();
		LinkedList<Integer> n2 = new LinkedList<>();

		boolean odd = true;
		int i; 
		for(i = n - 1; i >=0; i--){
			int d = digits[i];
			if(d==0) break;
			if(odd) n1.add(d);
			else n2.add(d);
			odd = !odd;
		}
		for( /*empty*/ ; i >=0; i--){
			LinkedList<Integer> listToAdd = null;
			int diff = n2.size() - n1.size();
			if(diff == 0){ //can’t be both 0
				listToAdd = (n1.getLast() > n2.getLast())?n2:n1;
			} else {
				if(diff > 0){
					listToAdd = n1.isEmpty()?n2:n1;
				} else {
					listToAdd = n2.isEmpty()?n1:n2;
				}
			}
			listToAdd.add(listToAdd.size()-1,0); 
		}

		int ret = 0;
		Iterator<Integer> it1 = n1.iterator();
		Iterator<Integer> it2 = n2.iterator();
		System.out.println(n1);
		System.out.println(n2);
		int p  =1;
		while( it1.hasNext() || it2.hasNext()){
			if(it1.hasNext()) ret+=p*it1.next().intValue();
			if(it2.hasNext()) ret+=p*it2.next().intValue();
			p*=10;

		}

		return ret ;
	}
	
	public static void main(String[] args) {
		int [] digits = { 3, 0,0,1, 7,6 ,0};
		System.out.println("Sum is " + getMinSum(digits));
		
		
	}
	
}

public class MinPairSumFromDigits {

	static long minPairSumFromNumbersBuiltFromDigits(int digits[]) throws Exception{
		if(digits == null){
			throw new Exception("Invalid argument " + digits);
		} else {
			for(int i : digits){
				if(i < 0 || i > 9){
					throw new Exception("Invalid argument " + i);
				}
			}
		}
		
		Arrays.sort(digits);
		int n = digits.length;
		
		List<Integer> digitsOfNum1 = new LinkedList<Integer>();
		List<Integer> digitsOfNum2 = new LinkedList<Integer>();
		int leadingDigitNum1 = 0;
		int begin = 0;
		if(n%2 == 1){
			leadingDigitNum1 = digits[begin++];
		}
		
		for(int i = n-1; i >= begin; i--){
			if(i%2 == 0){
				digitsOfNum2.add(digits[i]);
			} else {
				digitsOfNum1.add(digits[i]);
			}
		}
		digitsOfNum1.add(leadingDigitNum1);
		
		String num1Str = "";
		String num2Str = "";
		
		for(int i : digitsOfNum1){
			num1Str = i + num1Str; 
		}
		for(int i : digitsOfNum2){
			num2Str = i + num2Str; 
		}
		
		long num1 = Long.parseLong(num1Str);
		long num2 = Long.parseLong(num2Str);
		
		System.out.println("num1\t"+num1 + "\tnum2\t" + num2);
		return num1+num2;
	}
	
	public static void main(String[] args) throws Exception{
		   int testcase1[] = { 1 , 2 , 7 , 8 , 9 };
		   int result1 = 207;
		   
		   int testcase2[] = { 1 , 2 , 5 , 7 , 8 , 9 };
		   int result2 = 437;
		   
		   System.out.println(Arrays.toString(testcase1));
		   long x = minPairSumFromNumbersBuiltFromDigits(testcase1);
		   System.out.println(result1 + "\t" + x);

		   System.out.println(Arrays.toString(testcase2));
		   x = minPairSumFromNumbersBuiltFromDigits(testcase2);
		   System.out.println(result2 + "\t" + x);
	   }
}

unsigned int findMinSum(vector<unsigned int> digits) {
	vector<unsigned int> hash = vector<unsigned int>(10,0);
	unsigned int operands[2] = {0,0};
	for(auto dig : digits) {
		hash[dig]++;
	}

	int turn = 0;
	for(int i = 0; i < 10; i++) {
		while(hash[i] > 0) {
			operands[turn] = operands[turn] * 10 + i;
			turn = (turn + 1) % 2;
			hash[i]--;
		}
	}
	return operands[0] + operands[1];
}

Handles zeroes. Considers '01' as invalid candidate number i.e. a number either must start with a non-zero digit or be equal to a zero.

public class MinSumOfTwoFormedNum {

	public static void main(String[] args) {
		int []digits = new int[] {2, 7, 9, 8, 1};
		int expectedAns = 129+78; // (= 207)
		Assert.assertEquals(expectedAns, minSum(digits));
		digits = new int[] {1, 0, 0, 0, 0};
		expectedAns = 1000+0; // (= 1000)
		Assert.assertEquals(expectedAns, minSum(digits));
		digits = new int[] {1, 0, 0, 1, 0};
		expectedAns = 100+10; // (= 110)
		digits = new int[] {1, 0, 0, 1, 3, 0};
		expectedAns = 100+103; // (= 203)
		Assert.assertEquals(expectedAns, minSum(digits));

		System.out.println("All good!");
	}

	private static int minSum(int[] digits) {
		int sum = 0;
		countSort(digits);
		int nonZeroDigits = digits.length;
		int zeroDigits = 0;
		while(digits[zeroDigits] == 0) {
			nonZeroDigits--; 
			zeroDigits++;
		}
		if (nonZeroDigits == 0) return 0;
		if (nonZeroDigits == 1) return (int) (digits[digits.length-1]*Math.pow(10, zeroDigits-1));
		if (zeroDigits >= 1) {
			digits[0] = digits[zeroDigits];
			digits[zeroDigits] = 0;
		}
		if (zeroDigits >= 2) {
			digits[1] = digits[zeroDigits+1];
			digits[zeroDigits+1] = 0;
		}
		long factor = 1;
		for (int i = digits.length-1; i >= 0;) {
			sum += factor*digits[i--];
			if (i >= 0) sum += factor*digits[i--]; 
			factor *= 10;
		}
		return sum;
	}

	private static void countSort(int[] digits) {
		int counts[] = new int[10];
		for (int i = 0; i < digits.length; i++) {
			counts[digits[i]]++;
		}
		int idx = 0;
		for (int i = 0; i < counts.length; i++) {
			while(counts[i]-- > 0) {
				digits[idx++] = i;
			}
		}
	}

}

int[] arr={1,5,8,2,6,9,2,4,2,0,0,0};
	Arrays.sort(arr);
	int arrlen=arr.length;
	String fStr="";
	String lStr="";
	for(int i=0;i<arrlen;i++){
		if(i%2==0){
			fStr+=""+arr[i];
		}else{
		  	lStr+=""+arr[i];
		}
	}
	int num1=Integer.parseInt(fStr.trim());
	int num2=Integer.parseInt(lStr.trim());
	System.out.println(fStr+" + "+lStr+" = "+(num1+num2));