algoadvance

Leetcode 2160. Minimum Sum of Four Digit Number After Splitting Digits

Problem Statement

You are given a positive integer num consisting of exactly four digits. You need to split num into two new integers new1 and new2 by rearranging its digits. The task is to return the minimum possible sum of new1 and new2.

Example:

The possible pairs of new1 and new2 after rearranging the digits can be (29, 23) leading to the minimum sum 52.

Clarifying Questions

  1. Can num have leading zeros?
    • No, num is a positive integer with exactly four digits (1000 to 9999).
  2. Do new1 and new2 need to be non-zero integers?
    • Yes, new1 and new2 should be non-zero integers formed by using exactly two of the digits from num.
  3. Is there any constraint on which digits should go into new1 and new2?
    • No, you can use any pair of digits to form the integers, but each digit from num must be used exactly once.

Strategy

To achieve the minimum sum:

  1. Extract and sort the digits of num.
  2. Use the smallest two digits to form one number and the larger two digits to form another, ensuring they are combined in such a way that their sum is minimized.

Steps:

  1. Extract digits from num.
  2. Sort these digits.
  3. Form the smallest possible integers using these digits as described.

Code

Here’s the implementation of the solution strategy in C++:

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

int minimumSum(int num) {
    // Extract digits
    std::vector<int> digits;
    while (num > 0) {
        digits.push_back(num % 10);
        num /= 10;
    }
    
    // Sort the digits
    std::sort(digits.begin(), digits.end());
    
    // Form two numbers such that their sum is minimized
    int new1 = digits[0] * 10 + digits[2];
    int new2 = digits[1] * 10 + digits[3];
    
    return new1 + new2;
}

// Driver code to test the function
int main() {
    int num = 2932;
    std::cout << "Minimum sum: " << minimumSum(num) << std::endl; // Output should be 52
    return 0;
}

Time Complexity

Overall, the time complexity is O(1) considering the constraints.

This ensures that the solution is optimal and efficient for the given problem constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI