LeetCode 3754 - Concatenate Non-Zero Digits and Multiply by Sum I

LeetCode Problem 3754

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem asks us to process an integer n and construct a new number using only its non-zero digits. These digits must remain in the same order in which they originally appear. After constructing this new integer x, we calculate the sum of its digits and then return the product:

$$x \times \text{sum of digits of } x$$

In simpler terms, we scan through the digits of n, ignore every 0, and glue together the remaining digits to form a new number. Then we compute the digit sum of this new number and multiply the two values together.

For example, if n = 10203004, the digits are:

1, 0, 2, 0, 3, 0, 0, 4

Ignoring the zeros leaves:

1, 2, 3, 4

Concatenating them gives:

x = 1234

The sum of digits in x is:

1 + 2 + 3 + 4 = 10

The final result is:

1234 × 10 = 12340

The input is a single integer n, where:

$$0 \le n \le 10^9$$

This constraint is small. Even the maximum value has at most 10 digits, so any algorithm that scans the digits once will be extremely efficient.

There are several important edge cases to consider. If n = 0, then there are no non-zero digits, so x = 0, the digit sum is 0, and the answer is 0. Another edge case occurs when all digits except one are zero, such as 1000, where the resulting number is simply 1. We should also consider numbers containing only zeros after a leading digit, or numbers with no zeros at all, since both scenarios affect how the concatenation behaves.

Approaches

Brute Force Approach

A straightforward way to solve the problem is to first convert the integer n into a string. We can iterate through each character, skip '0', and collect all non-zero digits into another string. After constructing the new string, we convert it back to an integer to get x.

Then, to compute the sum of digits of x, we could again convert x into a string and sum its digits. Finally, we return:

$$x \times \text{digit sum}$$

This approach is correct because it explicitly follows the problem statement. We reconstruct the number exactly as required and compute the sum afterward.

Although this method is already fast enough due to the small constraints, it performs multiple conversions between integers and strings and processes digits more than once.

Optimal Approach

A better approach is to process everything in a single pass through the digits of n.

The key observation is that while building x, we already know each non-zero digit. Since the digit sum of x is simply the sum of those same digits, we can compute both values simultaneously.

We iterate through the digits of n:

• Ignore zeros.
• Append each non-zero digit to x using place-value arithmetic.
• Add the digit to a running sum.

To append a digit numerically, we use:

$$x = x \times 10 + digit$$

This avoids string conversions and allows us to compute both x and the digit sum in one traversal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d)	O(d)	Uses string conversion and extra storage for concatenation
Optimal	O(d)	O(1)	Builds x and digit sum simultaneously in one pass

Here, d is the number of digits in n. Since n ≤ 10^9, d ≤ 10.

Algorithm Walkthrough

1. Convert n into a string so that we can iterate through its digits in left-to-right order.
2. Initialize two variables:

• x = 0, which will store the concatenated non-zero digits.
• digit_sum = 0, which will track the sum of digits in x.

3. Iterate through each digit character in the string representation of n.
4. Convert the current character into an integer digit.
5. If the digit is 0, skip it because the problem explicitly tells us to concatenate only non-zero digits.
6. If the digit is non-zero:

• Append it to x using:

$$x = x \times 10 + digit$$

This shifts existing digits left and places the new digit at the end.

• Add the digit to digit_sum.

7. After processing all digits, return:

$$x \times digit_sum$$

Why it works

The algorithm maintains an invariant during iteration: after processing each digit, x contains exactly the concatenation of all non-zero digits seen so far, in the correct order, and digit_sum equals the sum of those digits.

Since every digit is processed exactly once and zeros are skipped, by the end of the traversal x is precisely the required number and digit_sum is its correct digit sum. Multiplying them produces the required answer.

Python Solution

class Solution:
    def sumAndMultiply(self, n: int) -> int:
        x = 0
        digit_sum = 0

        for char in str(n):
            digit = int(char)

            if digit == 0:
                continue

            x = x * 10 + digit
            digit_sum += digit

        return x * digit_sum

The implementation begins by initializing x and digit_sum to zero. These variables track the constructed number and the sum of its digits.

We convert n to a string so we can process digits in their original left-to-right order. For each character, we convert it into an integer digit.

If the digit is zero, we skip it immediately. Otherwise, we update x using decimal place shifting:

$$x = x \times 10 + digit$$

At the same time, we add the digit to digit_sum. This ensures both required values are computed in a single pass.

Finally, the function returns the product of x and digit_sum.

Go Solution

func sumAndMultiply(n int) int64 {
	x := int64(0)
	digitSum := int64(0)

	for _, ch := range []byte(strconv.Itoa(n)) {
		digit := int64(ch - '0')

		if digit == 0 {
			continue
		}

		x = x*10 + digit
		digitSum += digit
	}

	return x * digitSum
}

The Go solution follows the same logic as the Python version. The main difference is that Go requires explicit integer type management.

Because the function signature returns int64, both x and digitSum are stored as int64 values to avoid repeated type conversions.

Go also requires strconv.Itoa(n) to convert an integer into a string for digit iteration. This means the following import is required:

import "strconv"

Since the input size is very small, there are no concerns about performance or memory usage. Integer overflow is also not an issue because the largest possible result comfortably fits inside int64.

Worked Examples

Example 1

Input: n = 10203004

We process each digit one by one.

Current Digit	Non-Zero?	x Before	x After	digit_sum
1	Yes	0	1	1
0	No	1	1	1
2	Yes	1	12	3
0	No	12	12	3
3	Yes	12	123	6
0	No	123	123	6
0	No	123	123	6
4	Yes	123	1234	10

Final values:

• x = 1234
• digit_sum = 10

Result:

$$1234 \times 10 = 12340$$

Example 2

Input: n = 1000

Current Digit	Non-Zero?	x Before	x After	digit_sum
1	Yes	0	1	1
0	No	1	1	1
0	No	1	1	1
0	No	1	1	1

Final values:

• x = 1
• digit_sum = 1

Result:

$$1 \times 1 = 1$$

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	We scan each digit exactly once
Space	O(1)	Only a few variables are used

Here, d is the number of digits in n. Since n ≤ 10^9, the maximum number of digits is only 10, making the algorithm effectively constant time in practice.

The space complexity is constant because we only maintain two integer variables regardless of input size.

Test Cases

solution = Solution()

assert solution.sumAndMultiply(10203004) == 12340  # Example 1
assert solution.sumAndMultiply(1000) == 1  # Example 2

assert solution.sumAndMultiply(0) == 0  # All digits are zero
assert solution.sumAndMultiply(5) == 25  # Single non-zero digit
assert solution.sumAndMultiply(111) == 9  # No zeros, repeated digits
assert solution.sumAndMultiply(909) == 162  # Zeros in the middle
assert solution.sumAndMultiply(100000001) == 22  # Non-zero digits at both ends
assert solution.sumAndMultiply(123456789) == 5555555505  # Large digit sum
assert solution.sumAndMultiply(1000000000) == 1  # Maximum constraint with many zeros
assert solution.sumAndMultiply(101010101) == 625  # Alternating zeros

Test	Why
10203004	Validates the main example
1000	Tests a single remaining non-zero digit
0	Ensures empty non-zero digit set becomes x = 0
5	Tests a single-digit non-zero number
111	Verifies repeated non-zero digits
909	Ensures zeros are skipped correctly
100000001	Tests non-zero digits at both ends
123456789	Verifies larger concatenation and digit sum
1000000000	Tests upper constraint boundary
101010101	Checks alternating zero handling

Edge Cases

Input is 0

This is the most important special case. Since there are no non-zero digits, the problem explicitly defines x = 0. A careless implementation might accidentally treat an empty result as invalid or fail during conversion. Our implementation handles this naturally because x and digit_sum start at zero, and no digit updates occur.

Only One Non-Zero Digit Exists

Inputs like 1000 or 9000000 contain exactly one non-zero digit. A buggy implementation might incorrectly concatenate extra zeros or miscalculate the sum. Our algorithm correctly skips zeros and only appends non-zero digits, leaving x equal to the lone digit.

No Zeros in the Number

For values such as 12345, every digit contributes to both x and digit_sum. This verifies that the algorithm behaves correctly even when no filtering occurs. Since we always append non-zero digits and sum them simultaneously, the result remains accurate.

Zeros Appear Between Non-Zero Digits

Numbers like 1020304 can expose ordering mistakes. The digits must remain in their original order after zeros are removed. Our implementation preserves order naturally because digits are processed left to right and appended numerically using x = x * 10 + digit.