LeetCode 1317 - Convert Integer to the Sum of Two No-Zero Integers
Brute Force
Brute force is a possible solution because the domain of n is small: 2 <= n <= 10^4.
Time Complexity: O(n)
Space Complexity: O(1)
Iterative
The idea is to check each digit of n, starting with the rightmost digit or the ones place. If the digit is zero, then we can split that into 1 * (magnitude of the digit) and 9 * (magnitude of the digit). If the digit is one, then we can split it into 2 * and 9 * the magnitude. Otherwise, for any other digit (or if we've reached the leftmost and the digit is one), we can just split the digit into (num - 1) * magnitude and 1 * magnitude because this will not result in creating any new zero digits. In the first two cases, we want to ensure that we don't create a new zero digit after splitting the rightmost digit. We iterate from right to left, removing the rightmost digit of n after each iteration is complete, and increasing the magnitude. After iterating over every digit, we return the sums of the two designated splits, as a list.
Time Complexity: O(log n)
Space Complexity: O(1)