Restore The Array - Practice Coding Problems

Restore The Array - Problem

A program was supposed to print an array of integers. Due to a bug, the program forgot to print whitespaces and the array is printed as a string of digits s.

All we know is that:

All integers in the original array were in the range [1, k]
There are no leading zeros in any of the integers

Given the string s and the integer k, return the number of possible arrays that can be printed as s using the mentioned program.

Note: Since the answer may be very large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: s = "1317", k = 2000

› Output: 8

💡 Note: Possible arrays: [1,3,1,7], [1,3,17], [1,31,7], [1,317], [13,1,7], [13,17], [131,7], [1317]. All numbers are ≤ 2000.

Example 2 — Small k

$ Input: s = "2020", k = 30

› Output: 1

💡 Note: Only possible array is [20,20]. Cannot take "2020" or "202" as they exceed k=30.

Example 3 — Leading Zero

$ Input: s = "1012", k = 50

› Output: 2

💡 Note: Possible arrays: [1,0,1,2] is invalid (0 not in range [1,k]), [10,12] and [1,0,12] are invalid, only [10,1,2] and [1,012] but 012 has leading zero, so only [10,1,2] is valid. Actually [1,12] is also valid, so answer is 2: [10,1,2] and [1,12].

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only digits
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Digit string s="1317" and constraint k=2000

Process

Find all ways to split into numbers [1,k] with no leading zeros

Output

Count of valid arrays: 8 different ways

Key Takeaway

🎯 Key Insight: Use DP where dp[i] = number of ways to restore array from position i onwards

Asked in

G Google 25 a Amazon 18 f Facebook 15

The key insight is to use dynamic programming where each position represents a subproblem: "how many ways to restore from this position onwards". We can either use top-down memoization or bottom-up DP. The optimal approach is Bottom-Up DP with time complexity O(n × log k) and space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(n × log k)	O(n)	Cache recursive results to avoid recomputation
Bottom-Up Dynamic Programming	O(n × log k)	O(n)	Build solution iteratively from right to left
Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible ways to split the string recursively

Memoized Recursion — Algorithm Steps

Use recursion with memoization
Store results for each starting index
Return cached result if already computed
Otherwise compute and cache before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

Compute

Calculate result for each index the first time

Cache

Store the result in memo table

Reuse

Return cached result for repeated subproblems

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

const int MOD = 1000000007;
const int MAXN = 100005;
long long memo[MAXN];
int computed[MAXN];

long long dp(const char* s, int k, int index, int len) {
    if (index == len) {
        return 1;
    }
    
    if (computed[index]) {
        return memo[index];
    }
    
    if (s[index] == '0') {
        memo[index] = 0;
        computed[index] = 1;
        return 0;
    }
    
    long long ways = 0;
    long long currentNum = 0;
    
    for (int i = index; i < len; i++) {
        currentNum = currentNum * 10 + (s[i] - '0');
        if (currentNum > k) {
            break;
        }
        ways = (ways + dp(s, k, i + 1, len)) % MOD;
    }
    
    memo[index] = ways;
    computed[index] = 1;
    return ways;
}

int solution(char* s, int k) {
    int len = strlen(s);
    memset(computed, 0, sizeof(computed));
    return dp(s, k, 0, len);
}

int main() {
    char s[100001];
    int k;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log k)

Each of n positions computed once, each taking O(log k) time to try numbers up to k

⚡ Linearithmic

Space Complexity

O(n)

Memoization table stores results for n positions plus recursion stack

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler