Sum of All Digit Subsequences
JavaView on GFG
Problem Overview
The task is the sum of every digit across every non-empty subsequence, not the sum of the integers those subsequences spell.
Intuition
The task is the sum of every digit across every non-empty subsequence, not the sum of the integers those subsequences spell. Fix one digit. Each of the other n minus 1 digits may either join that subsequence or stay out, so that fixed digit appears in exactly 2 to the power n minus 1 subsequences. Its contribution is therefore its value times that power. Summing over every digit factors into the plain digit sum multiplied by the same power. The product is taken modulo 1000000007. Reading the string once to total the digits is unavoidable, and the power is computed with binary exponentiation.
Algorithm
- 1Return 0 when the string is empty.
- 2Add every digit value into a running sum.
- 3Compute 2 to the power n minus 1 under the modulus with binary exponentiation.
- 4Return the digit sum times that power, reduced modulo 1000000007.
Example Walkthrough
Input: s = "123"
- 1. The digits sum to 6. There are 2 to the power 2 equals 4 subsequences that contain any fixed digit.
- 2. Each digit therefore contributes four times its value, for a total of 24.
- 3. Listing the subsequences [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] and adding their digits confirms 24.
Output: 24
Common Pitfalls
- • Count digit appearances inside subsequences. Do not treat a subsequence as a multi-digit integer with place values.
- • Use modular multiplication. For long strings, 2 to the power n minus 1 overflows a plain 32 bit integer.
- • An empty string has no subsequences, so return 0 before computing a negative exponent.
- • Zero digits still occupy subsequence slots. They add nothing to the digit sum, but they still count toward n.
Sum of All Digit Subsequences.java
Java
// Approach: Every digit sits in exactly 2^(n - 1) non-empty subsequences,
// because each of the other n - 1 digits may be kept or dropped. Sum all
// digits once, multiply by 2^(n - 1) under the modulus, and return that
// product. The string must be read, so the bound is already tight.
// Complexity: O(n) time, O(1) extra space.
class Solution {
public int subsequenceSum(String s) {
int n = s.length();
if (n == 0) {
return 0;
}
final int mod = 1_000_000_007;
long sum = 0;
for (int i = 0; i < n; i++) {
sum += s.charAt(i) - '0';
}
return (int) ((sum % mod) * modPow(2, n - 1, mod) % mod);
}
private long modPow(long base, long exp, int mod) {
long res = 1;
base %= mod;
while (exp > 0) {
if ((exp & 1) == 1) {
res = res * base % mod;
}
base = base * base % mod;
exp >>= 1;
}
return res;
}
}
Was this solution helpful?