Given a four-digit positive integer say num, split the given integer to form two new numbers say num1 and num2. All the digits present in num should be used and leading zeros are allowed for the formation of new numbers. Return the minimum possible sum of new numbers num1 and num2.
Example 1:
Input: num = 2832
Output: 51
Explanation:
Some possible pairs of numbers [num1, num2]:
[2, 832] = 2 + 832 = 834
[28, 32] = 28 + 32 = 60
[283, 2] = 283 + 2 = 285
[23, 28] = 23 + 28 = 51
etc.
The minimum possible sum of new numbers that can be obtained is [23, 28] = 23 + 28 = 51
Example 2:
Input: num = 5008
Output: 13
Explanation:
Some possible pairs of numbers [num1, num2]:
[00, 58] = 0 + 58 = 58
[00, 85] = 0 + 85 = 85
[05, 08] = 5 + 8 = 13
[50, 08] = 50 + 8 = 58
etc.
The minimum possible sum of new numbers that can be obtained is [05, 08] = 5 + 8 = 13
Approach 1: Using Sorting.
To solve this problem we do not need to generate all possible combinations of numbers and the length of num1 and num2 is going to be equal in all ideal cases. For creating the two smallest numbers that give you the minimum sum, the smaller digits should appear at the most significant position.
Below are the steps to solve this:
1. Convert the given 4-digit number into an array of digits.
2. Sort the array into increasing order.
3. Traverse the array from 0 to size and create two numbers:
- num1 is going to be formed by digits present at odd positions in the array.
- num2 is going to be formed by digits present at even positions in the array.
4. Return the sum of both digits (num1 + num2).
Below is the Code Implementation:
/*C++ Code for Find Minimum Sum of Two Number Formed from Splitting Four Digit Number.*/ #include<iostream> #include<algorithm> #include<vector> using namespace std; int minimumSum(int num){ int num1 = 0, num2 = 0; int ans = 0; //using vector instead of array vector<int> vnum; //breaking 4 digit number and storing //each digit into integer array while(num){ int rem = num%10; vnum.push_back(rem); num = num/10; } //sorting the created list in ascending order sort(vnum.begin(), vnum.end()); //forming num1 and num2 for(int i = 0; i < vnum.size(); i++){ if(i % 2 == 0) num1 = num1*10 + vnum[i]; else num2 = num2*10 + vnum[i]; } return num1 + num2; } int main(){ int num = 5008; //function call cout<<minimumSum(num); }
13
- Time Complexity: O(nlogn) because we also have to perform sorting.
- Space Complexity: O(n) where n is the number of digits present.
Approach 2: Using String.
The logic of this approach is almost the same as the previous one but the only benefit is that you don't have to deal with the step of creating an array of digits.
Below are the steps to solve this problem:
1. Convert the given number into a string.
2. Sort the created string in ascending order.
3. Traverse the sorted string from 0 to size and create two numbers:
- num1 is going to be formed by digits present at odd positions in the string.
- num2 is going to be formed by digits present at even positions in the string.
4. Return the sum of both numbers (num1 + num2).
Below is the Code Implementation:
/*C++ Code for Find Minimum Sum of Two Number Formed from Splitting Four Digit Number.*/ #include<iostream> #include<algorithm> using namespace std; int minimumSum(int num){ int num1 = 0, num2 = 0; int ans = 0; //converting number to string string str = to_string(num); //sorting the convert string in ascending order sort(str.begin(), str.end()); //forming num1 and num2 for(int i = 0; i < str.size(); i++){ if(i % 2 == 0) num1 = num1*10 + (str[i] - '0'); else num2 = num2*10 + (str[i] - '0'); } return num1 + num2; } int main(){ int num = 5008; //function call cout<<minimumSum(num); }
13
- Time Complexity: (nlogn)
- Space Complexity: O(n)
I hope you found this post useful, please write your comments below if you want to give us any feedback to improve our content.
No comments:
Post a Comment