• 8

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
13
of 13 vote

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

And why does it work? Because it's clearly not how two numbers in the answer are built however the answer is the same - 207.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Try adding two numbers, you would find all that matters is the order of magnitude of a digit and not which of the two numbers that a digit belongs. (e.g. 178+29 = 128+79 = 179+28 = 129+78)

Comment hidden because of low score. Click to expand.
0

nice one Mr. Manoj

Comment hidden because of low score. Click to expand.
0

The result in the question is built differently but following the same logic.
Firsty you take 1st last digit for first number, then 2 last digits for the second, then 2 last digits for the first number, then .... You can take 2 at once, because it doesn't matter about the variation in the same level of the number.

So it was like 1 2 7 8 9 -> 9 _ -> 9 78 -> 129 78

Comment hidden because of low score. Click to expand.
3
of 3 vote

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;
}

Comment hidden because of low score. Click to expand.
2

for sorting array of digits, we have linear ( O(n) ) algorithms, e.g. counting sort.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

the code does not work for inputs that contain zeros, like 11110. For this input sum should be 112, instead I get 22.

Comment hidden because of low score. Click to expand.
0

@azil Can you explain why 11110 should be 112?

Comment hidden because of low score. Click to expand.
0

because the smallest numbers that can be created of those digits are 101 and 11 and their sum is 112.

Comment hidden because of low score. Click to expand.
1
of 1 vote

@azil. Ok, and what about 011 + 11? The sum is 22. All the digits are contained in the array and it's the smallest sum.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

Why does the approach work?

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 4 vote

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));
}

Comment hidden because of low score. Click to expand.
2

You should handled if X[0]=0

Comment hidden because of low score. Click to expand.
0

kidding code boy

Comment hidden because of low score. Click to expand.
-1
of 1 vote

1 - You create too many redundunt String objects
2 - You don't process zeros. For example if you have {0, 0, 1, 2} sorted input array your sum will be 01 + 02 = 3. But I think it should be 10 + 20 = 30

Comment hidden because of low score. Click to expand.
-2

public void findMinSum(int[] x){
Arrays.sort(x);
String first = "";
String second = "";
for(int i=0; i<x.length; i=i+2)
{
first+=x[i];
second+=x[i+1];
}
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));
}

Comment hidden because of low score. Click to expand.
0

@Pirate : If the input digits are 3,5,7,9 ; then your code will return 3579 for string 2 (definitely not the minimal sum) . I guess the minimal sum here would be 37 + 59 = 96.

Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
* 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,
);

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Strange "programming language used" comment in there...

And yeah, strange language used (php! Yuck!).

Comment hidden because of low score. Click to expand.
1
of 1 vote

You should revisit this condition inside the while loop.

while (isset(\$array[\$i]))

Reason: You're accessing the next two indexes of \$i inside the while loop. But checking only the existence of \$i.

Comment hidden because of low score. Click to expand.
0

/**
* 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++];
if (isset(\$array[\$i])) {
\$numberTwo .= \$array[\$i++];
}
}

return array(
0 => (int) \$numberOne,
1 => (int) \$numberTwo,
);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ");
try {
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();
}

}
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

Why not explain an algorithm rather than giving a program?

Comment hidden because of low score. Click to expand.
0

@confused_banda, May be because developers understand program better than reading the text :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

From looking over the example given your algo does not give the right solution

1 8 2 9 7 => 1 2 7 8 9 => 12 + 789 = 901 which is not the right answer.

Even if you split it correctly (adding the ODD number of numbers, in the beginning, to the EVEN number left)

127 + 89 = 216 which is still not the right answer of 207.

The correct solutions would be 129 + 78 or 178 + 29

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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..

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.IOException;
import java.util.ArrayList;
import java.util.Collections;

public static void main(String[] args) throws IOException
{
System.out.println(" Enter the list of Integers ");

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 ++)

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));

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 2 vote

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];
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

the example given in the question wont work

Comment hidden because of low score. Click to expand.
0

gggg, it outputs 207, which is the correct answer.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

- 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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

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
} else {
}
} 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) {
} else {
}
} else {
num2 = num2 * 10 + x;
}
}
}

return num1 + num2;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
* 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);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

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

Arrays.sort(digits);

boolean odd = true;
int i;
for(i = n - 1; i >=0; i--){
int d = digits[i];
if(d==0) break;
odd = !odd;
}
for( /*empty*/ ; i >=0; i--){
int diff = n2.size() - n1.size();
if(diff == 0){ //can’t be both 0
} else {
if(diff > 0){
} else {
}
}
}

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));

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

int begin = 0;
if(n%2 == 1){
}

for(int i = n-1; i >= begin; i--){
if(i%2 == 0){
} else {
}
}

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);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}

}

Comment hidden because of low score. Click to expand.
-1
of 3 vote

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));

Comment hidden because of low score. Click to expand.
0

Why is it voted down? It is absolutely right.

Comment hidden because of low score. Click to expand.
0

Is there a reason why this one is not right?

Comment hidden because of low score. Click to expand.
0

you should not have 0 in the example

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.