Convert Integer to the Sum of Two No Zero Integers

First, I defined a function that checked whether an integer contains any 0 in its decimal representation:

bool checkZeroIntegers(int n) {
    for (; n > 0; n /= 10) {
        if (n % 10 == 0) {
            return false;
        }
    }
    return true;
}

Then, I simply iterated through all pairs of integers that sum to n, running checkZeroIntegers on both integers present in the pair. If both integers do not contain any zero integers, then we can simply return the pair.

for (int i = 1; i < n; ++i) {
    if (checkZeroIntegers(i) && checkZeroIntegers(n-i)) {
        return {i, n-i};
    }
}

code

class Solution {
public:
    vector<int> getNoZeroIntegers(int n) {
        for (int i = 1; i < n; ++i) {
            if (checkZeroIntegers(i) && checkZeroIntegers(n-i)) {
                return {i, n-i};
            }
        }
        return {};
    }
private:
    bool checkZeroIntegers(int n) {
        for (; n > 0; n /= 10) {
            if (n % 10 == 0) {
                return false;
            }
        }
        return true;
    }
};

complexity

• Time: O(n log(n))
• Space: O(1)

learnings

• for memory sparse situation, can be better to forgo the to_string approach and to just use division and modulo to accomplish the same thing
  • e.g. instead of converting an integer to a string and iterating through its numbers, we can accomplish the same thing with division and modulo operation

time taken

• 4 minutes and 53 seconds
  • i was carsick on the bus.... believe me guys...