algoadvance

Leetcode 3174. Clear Digits

Problem Statement

You are given a string num representing a non-negative integer. Rearrange the digits to form the smallest possible number that is divisible by three. If the input cannot be rearranged to a number divisible by three, return an empty string.

Clarifying Questions

  1. Input Constraints:
    • Is the input string guaranteed to contain only numerical characters (0-9)?
    • Can the input string be empty?
    • Are there leading zeros in the input string and should they be handled in the final result?
  2. Outputs:
    • Should the output preserve the leading zeros if the resultant number has leading zeros?
  3. Edge cases:
    • What is the expected output for an empty string?
    • If no rearrangement yields a number divisible by three, the output should be an empty string, correct?

Code

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

std::string smallestDivisibleByThree(std::string num) {
    if (num.empty()) return "";

    // Calculate the sum of digits
    int totalSum = 0;
    for (char ch : num) {
        if (!isdigit(ch)) return "";
        totalSum += (ch - '0');
    }

    // Check if current digits already divisible by 3
    if (totalSum % 3 == 0) {
        // sort digits to get smallest number
        std::sort(num.begin(), num.end());
        return num;
    }

    std::vector<int> digit_count(10, 0);
    for (char ch : num) {
        digit_count[ch - '0']++;
    }

    auto remove_digit = [&](int rem) {
        // Try to remove one digit with remainder 'rem'
        for (int i = rem; i < 10; i += 3) {
            if (digit_count[i] > 0) {
                digit_count[i]--;
                return true;
            }
        }
        return false;
    };

    bool adjusted = false;
    int remainder = totalSum % 3;

    // If totalSum % 3 is 1, try to remove one digit with remainder 1.
    // If not, remove two digits each with remainder 2.
    if (remainder == 1) {
        adjusted = remove_digit(1) || (remove_digit(2) && remove_digit(2));
    }
    // If totalSum % 3 is 2, try to remove one digit with remainder 2.
    // If not, remove two digits each with remainder 1.
    else if (remainder == 2) {
        adjusted = remove_digit(2) || (remove_digit(1) && remove_digit(1));
    }

    if (!adjusted) return "";

    std::string result;
    for (int i = 0; i < 10; ++i) {
        result += std::string(digit_count[i], '0' + i);
    }

    // Remove leading zeros unless it's the only digit
    int pos = 0;
    while (pos < (int)result.size() - 1 && result[pos] == '0') ++pos;
    result = result.substr(pos);
    
    return result.empty() ? "" : result;
}

int main() {
    std::string num = "123456";
    std::string result = smallestDivisibleByThree(num);
    std::cout << "Result: " << result << std::endl;  // Should print the smallest number divisible by three
    return 0;
}

Strategy

  1. Calculate Total Sum:
    • Sum all digits in the given string num.
  2. Check Divisibility:
    • Check if the current sum of digits is already divisible by 3. If so, sort the digits to form the smallest number and return.
  3. Adjusting Digits:
    • Use a function to remove digits to make the sum divisible by 3:
      • If the remainder of the sum when divided by 3 is 1, try removing one digit with a remainder of 1. If that’s not possible, remove two digits each with a remainder of 2.
      • If the remainder is 2, try removing one digit with a remainder of 2. Otherwise, remove two digits each with a remainder of 1.
  4. Form Result:
    • Construct the resultant number from the adjusted digit count ensuring the smallest possible value by sorting.
    • Handle leading zeros appropriately.

Time Complexity

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