3754. Concatenate Non-Zero Digits and Multiply by Sum I
Problem Description
You are given an integer n.
Your task is to build a new integer x by taking only the non-zero digits of n and joining them together while keeping their original left-to-right order. In other words, you remove every 0 from the number and keep what remains as a single integer. If n has no non-zero digits at all (for example, n is made up entirely of zeros), then x = 0.
After forming x, compute sum, which is the sum of all the digits in x.
Finally, return the result of x * sum.
For example, if n = 100, the only non-zero digit is 1, so x = 1 and sum = 1, giving a result of 1 * 1 = 1. If n = 235, then x = 235 and sum = 2 + 3 + 5 = 10, giving a result of 235 * 10 = 2350.
How We Pick the Algorithm
Why Simulation / Basic DSA?
This problem maps to Simulation / Basic DSA through a short path in the full flowchart.
Extracting digits one by one and reconstructing the number from only non-zero digits is a straightforward simulation of digit processing.
Open in FlowchartIntuition
The problem really asks for two simple things: a number x made of the non-zero digits, and the digit sum s. Both can be computed at the same time by walking through the digits of n.
The natural way to look at a number's digits one by one is to repeatedly take n % 10 (which gives the last digit) and then do n //= 10 (which drops that last digit). This lets us scan every digit from right to left.
For each digit v we extract, we always add it to the running sum s, because every digit contributes to the digit sum (and zeros add nothing anyway, so including them is harmless).
The trickier part is rebuilding x from only the non-zero digits while keeping their original order. Since we are reading digits from right to left, the first non-zero digit we meet is actually the last digit of x, the next one is the second-to-last, and so on. To place each non-zero digit at its correct position, we keep a multiplier p that starts at 1. Whenever we see a non-zero digit v, we add p * v to x and then multiply p by 10. This way the earliest-found digit lands in the ones place, the next one in the tens place, and so on—exactly reconstructing the non-zero digits in their original left-to-right order. Zeros are skipped, so they never shift the positions, which is precisely what "concatenating non-zero digits" means.
Once the loop ends, x holds the concatenated non-zero number and s holds the digit sum, so we simply return x * s.
Pattern Learn more about Math patterns.
Solution Approach
Solution 1: Simulation
We simulate the operation by processing the number digit by digit. While processing each digit, we concatenate the non-zero digits to form a new integer x and calculate the digit sum s. Finally, we return x * s.
We start by initializing three variables:
p = 1: a place-value multiplier used to position each non-zero digit correctly insidex.x = 0: the integer built from the non-zero digits.s = 0: the running sum of digits.
We then loop while n is non-zero. In each iteration:
- Extract the last digit with
v = n % 10. - Add it to the digit sum:
s += v. Since zero contributes nothing, it is safe to always do this. - If
vis non-zero, place it intoxusingx += p * v, then advance the multiplier withp *= 10. Because we read digits from right to left, the multiplier ensures each non-zero digit lands in its proper position, reproducing the original left-to-right order. - Drop the last digit with
n //= 10.
When the loop finishes, x holds the concatenated non-zero digits and s holds the digit sum, so we return x * s.
The time complexity is O(\log n), since the number of digits in n is proportional to \log n. The space complexity is O(1), as only a constant number of variables are used.
Example Walkthrough
Let's trace the algorithm with n = 4080.
We expect to remove the zeros, so x should be 48, the digit sum s should be 4 + 8 = 12, and the answer should be 48 * 12 = 576.
Initialization: p = 1, x = 0, s = 0.
We loop while n is non-zero, reading digits from right to left.
Iteration 1: n = 4080
- Extract last digit:
v = 4080 % 10 = 0 - Add to sum:
s = 0 + 0 = 0 vis0, so we skip updatingxandp. Zeros don't take up a position.- Drop last digit:
n = 4080 // 10 = 408 - State:
p = 1,x = 0,s = 0
Iteration 2: n = 408
- Extract last digit:
v = 408 % 10 = 8 - Add to sum:
s = 0 + 8 = 8 vis non-zero: place it withx += p * v = 0 + 1 * 8 = 8, then advancep = 1 * 10 = 10. The8lands in the ones place.- Drop last digit:
n = 408 // 10 = 40 - State:
p = 10,x = 8,s = 8
Iteration 3: n = 40
- Extract last digit:
v = 40 % 10 = 0 - Add to sum:
s = 8 + 0 = 8 vis0, so we skip updatingxandp. Notice this zero is ignored and does not shift the next digit's position.- Drop last digit:
n = 40 // 10 = 4 - State:
p = 10,x = 8,s = 8
Iteration 4: n = 4
- Extract last digit:
v = 4 % 10 = 4 - Add to sum:
s = 8 + 4 = 12 vis non-zero: place it withx += p * v = 8 + 10 * 4 = 48, then advancep = 10 * 10 = 100. The4lands in the tens place, sitting directly to the left of the8— exactly its original order.- Drop last digit:
n = 4 // 10 = 0 - State:
p = 100,x = 48,s = 12
Loop ends because n = 0.
Final result: x * s = 48 * 12 = 576. ✅
The key insight illustrated here is how the multiplier p only advances when a non-zero digit is found. The two zeros in 4080 are added to the sum (contributing nothing) but never consume a position in x, so the non-zero digits 4 and 8 collapse together in their original left-to-right order.
Solution Implementation
1class Solution:
2 def sumAndMultiply(self, n: int) -> int:
3 # place_value tracks the positional multiplier (1, 10, 100, ...)
4 # for building the number formed by non-zero digits only
5 place_value = 1
6 # compressed_number: the value built from non-zero digits (zeros removed)
7 # digit_sum: the sum of all digits of n
8 compressed_number = 0
9 digit_sum = 0
10
11 # Process n digit by digit, from least significant to most significant
12 while n:
13 digit = n % 10 # extract the current lowest digit
14 digit_sum += digit # accumulate the digit into the total sum
15
16 # Only non-zero digits contribute to the compressed number,
17 # and only they advance the place value (this drops zeros)
18 if digit:
19 compressed_number += place_value * digit
20 place_value *= 10
21
22 n //= 10 # move to the next digit
23
24 # Return the product of the zero-stripped number and the digit sum
25 return compressed_number * digit_sum
261class Solution {
2 public long sumAndMultiply(int n) {
3 // placeValue tracks the positional multiplier (1, 10, 100, ...)
4 // for building the number with zero digits removed
5 int placeValue = 1;
6
7 // compactedNumber: n with all zero digits stripped out
8 // digitSum: the sum of all digits of n
9 int compactedNumber = 0, digitSum = 0;
10
11 // Process each digit from least significant to most significant
12 for (; n > 0; n /= 10) {
13 int digit = n % 10;
14
15 // Always add the digit to the total digit sum
16 digitSum += digit;
17
18 // Only keep non-zero digits when rebuilding the number
19 if (digit != 0) {
20 compactedNumber += placeValue * digit;
21 // Advance to the next place value only for kept digits
22 placeValue *= 10;
23 }
24 }
25
26 // Multiply the compacted number by the digit sum
27 // Use 1L to force long arithmetic and avoid integer overflow
28 return 1L * compactedNumber * digitSum;
29 }
30}
311class Solution {
2public:
3 long long sumAndMultiply(int n) {
4 // placeValue tracks the current place (1, 10, 100, ...) used when
5 // rebuilding the number from its non-zero digits.
6 int placeValue = 1;
7 // compactNumber: the number formed by dropping all zero digits.
8 // digitSum: the sum of all digits (zeros contribute 0 anyway).
9 int compactNumber = 0;
10 int digitSum = 0;
11
12 // Process n digit by digit, from least significant to most significant.
13 for (; n > 0; n /= 10) {
14 int digit = n % 10; // Extract the current least-significant digit.
15 digitSum += digit; // Add it to the running digit sum.
16
17 // Only non-zero digits are kept when rebuilding compactNumber.
18 if (digit != 0) {
19 compactNumber += placeValue * digit; // Place digit at current position.
20 placeValue *= 10; // Advance to the next place value.
21 }
22 }
23
24 // Return the product of the compacted number and the digit sum.
25 // Use 1LL to force 64-bit multiplication and avoid overflow.
26 return 1LL * compactNumber * digitSum;
27 }
28};
291/**
2 * Computes the product of:
3 * 1. The number formed by removing all zero digits from `n` (compactNumber).
4 * 2. The sum of all digits of `n` (digitSum).
5 *
6 * Example: n = 1020
7 * - digitSum = 1 + 0 + 2 + 0 = 3
8 * - compactNumber = 12 (zeros stripped from 1020)
9 * - result = 12 * 3 = 36
10 *
11 * @param n - A non-negative integer to process.
12 * @returns The compacted number multiplied by the digit sum.
13 */
14function sumAndMultiply(n: number): number {
15 // Place value (1, 10, 100, ...) used to rebuild the number without zeros.
16 let placeValue = 1;
17 // The number reconstructed from `n` with all zero digits removed.
18 let compactNumber = 0;
19 // Running total of all digits in `n`.
20 let digitSum = 0;
21
22 // Process each digit from least significant to most significant.
23 while (n > 0) {
24 const digit = n % 10; // Extract the current lowest digit.
25 digitSum += digit; // Always add the digit to the sum.
26
27 // Only non-zero digits contribute to the compacted number.
28 if (digit !== 0) {
29 compactNumber += placeValue * digit; // Append digit at current place.
30 placeValue *= 10; // Advance to the next place value.
31 }
32
33 n = Math.floor(n / 10); // Drop the processed digit.
34 }
35
36 // Final result: compacted number scaled by the sum of digits.
37 return compactNumber * digitSum;
38}
39Time and Space Complexity
-
Time Complexity:
O(log n). Thewhileloop processes the integernone digit at a time. Each iteration removes the last digit vian //= 10, so the number of iterations equals the number of digits inn, which is approximatelylog₁₀(n). All operations inside the loop (modulo, addition, multiplication, division) run in constant time, giving a total time complexity ofO(log n). -
Space Complexity:
O(1). Only a fixed number of auxiliary variables (p,x,s,v) are used regardless of the size of the inputn. No additional data structures that scale with the input are allocated, so the space complexity is constant.
Pattern Learn more about how to find time and space complexity quickly.
Common Pitfalls
Pitfall 1: Advancing the place value for every digit instead of only non-zero digits
The most frequent mistake is multiplying place_value by 10 on every iteration, regardless of whether the current digit is zero. The whole point of this problem is to remove zeros, which means a zero digit should occupy no position in the compressed number. If you advance the place value for zeros too, you reintroduce the gaps you were supposed to eliminate.
Incorrect code:
while n:
digit = n % 10
digit_sum += digit
if digit:
compressed_number += place_value * digit
place_value *= 10 # BUG: advances even for zero digits
n //= 10
For n = 100, this would produce compressed_number = 1 * 100 = 100 instead of 1, because the two trailing zeros wrongly pushed the 1 two positions to the left.
Correct approach: advance place_value *= 10 inside the if digit: block, so only non-zero digits consume a positional slot.
if digit: compressed_number += place_value * digit place_value *= 10 # only advance when a digit is actually kept
Pitfall 2: Building the number as a string and forgetting the all-zero / empty case
A common alternative is to convert to a string, filter out '0', then call int() on the result. The trap is that filtering all zeros leaves an empty string, and int('') raises a ValueError.
Buggy version:
digits = ''.join(c for c in str(n) if c != '0')
x = int(digits) # ValueError when n is 0 or all zeros (e.g., n = 0)
Fix: guard against the empty result.
digits = ''.join(c for c in str(n) if c != '0')
x = int(digits) if digits else 0
s = sum(int(c) for c in str(n))
return x * s
The digit-by-digit simulation in the provided solution sidesteps this entirely: when every digit is zero, compressed_number simply stays 0, and the final product is 0—no special-casing required.
Pitfall 3: Computing the digit sum from the compressed number instead of the original n
Since removing zeros does not change the digit sum (zeros add nothing), it is tempting to think the order of operations doesn't matter. It indeed gives the same digit_sum, but a subtler mistake is summing digits after you have already modified n (e.g., reusing n in a second loop after it has been reduced to 0). Always accumulate digit_sum in the same single pass while n is still intact, as the provided code does, to avoid reading from a value that has already been consumed.
Ready to land your dream job?
Unlock your dream job with a 5-minute quiz for a personalized study roadmap!
Get My RoadmapWhat data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him
Want a Structured Path to Master System Design Too? Don’t Miss This!