Concatenate Non-Zero Digits and Multiply by Sum II - Solution & Explanation

Problem Overview: You process a sequence of digits and repeatedly form a number by concatenating only the non-zero digits while also tracking the running sum of digits. The task is to compute the required multiplied value efficiently without repeatedly rebuilding strings or recomputing sums.

Approach 1: Brute Force Concatenation and Recompute Sum (O(n^2) time, O(n) space)

The direct approach simulates the process literally. For every position, rebuild the number formed by concatenating all non-zero digits seen so far and recompute the sum of digits from scratch. This involves scanning the prefix each time and performing string concatenation or numeric construction. The repeated traversal causes the runtime to grow quadratically for long inputs. This approach is useful for validating correctness on small inputs but becomes inefficient quickly.

Approach 2: Prefix Sum + Rolling Concatenation (O(n) time, O(1) space)

A more efficient method processes the digits in a single pass. Maintain a running prefix sum of digits and a rolling number representing the concatenation of all non-zero digits encountered so far. When the current digit is non-zero, update the rolling value using value = value * 10 + digit. The running sum is updated using a standard prefix sum update. The required result at each step can then be computed directly using these maintained values without reconstructing previous digits. This eliminates repeated scans and reduces the runtime to linear.

This technique combines simple arithmetic with string-style digit processing and prefix sum accumulation. The key insight is that concatenation can be simulated numerically and the cumulative sum can be maintained incrementally.

Recommended for interviews: The prefix-sum plus rolling-number approach is the expected solution. The brute force version shows that you understand the direct interpretation of the problem, but interviewers typically look for the optimization that avoids rebuilding prefixes. Using incremental updates and constant extra space demonstrates stronger algorithmic thinking and familiarity with math-based digit manipulation.