Number of subsequences in a string divisible by N | Interview Question | Find count of subsequences which are divisible by 4.

raunit - in Coding
Given a large number as string (size upto 10^5). Find count of subsequences which are divisible by 4 ( asked in salesforce ). Find count of subsequences which are divisible by N.

Problem:

Given string s consisting of digits 0-9 and a number N, the task is to count the number of subsequences that are divisible by N.

Note:

The answer can be large; output the result modulo 109 + 7.

Example 1:

Input: s = "1234", N = 4

Output: 4

Explanation: The subsequences 4, 12, 24, and 124 are divisible by 4.

Example 2:

Input: s = "330", N = 6

Output: 4

Explanation: The subsequences 30, 30, 330, and 0 are divisible by 6.

Constraints:

  • 1 ≤ |s|*N ≤ 106

Expected:

  • Time Complexity: O(|s|*N)
  • Auxiliary Space: O(|s|*N)

Similar Interview Question:

Given a large number as a string (size up to 105), find the count of subsequences that are divisible by 4. Since the count could be very large, return the count modulo 109 + 7.

Details:

  • Date: Nov 29
  • Round: 3 (Coding)
  • Position: SMTS
  • Location: Hyderabad
  • Company: Salesforce
  • YOE: 5+

Experience:

I was asked to write the code in an editor. Initially, I struggled for a long time, feeling frustrated. However, the interviewer was very helpful, and their hints about what makes a number divisible by 4 guided me. Eventually, I came up with a solution and coded it.

We ran the code for a few test cases, and while there were a couple of bugs, we debugged it together to achieve a fully working solution. It was definitely not my best round, but I managed to cope and get over the line.

Additional Information:

Source: LeetCode Interview Experience

Interview Explanation:

The task was to count the subsequences of a given number string that are divisible by 4. Initially, I couldn't think of an optimal solution and started feeling anxious. After 10 minutes, the interviewer provided a helpful hint: "A number is divisible by 4 if the last two digits of the number are divisible by 4." This insight guided my approach:

  1. If the last two digits of the number are divisible by 4, then the possible last two digits are: 00, 04, 08, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, and so on.
  2. Iterate through the string considering each digit as the second-last digit of a potential subsequence:
    • If the digit is odd (1, 3, 5, 7, 9), the last digit in a subsequence can only be 2 or 6.
    • If the digit is even (0, 2, 4, 6, 8), the last digit in a subsequence can only be 0, 4, or 8.
  3. For each digit in the string (considered as the second-last digit), precompute the counts of relevant digits to its right:
    • If the digit is odd, count the occurrences of 2 and 6 to its right.
    • If the digit is even, count the occurrences of 0, 4, and 8 to its right.
    This precomputation can be done efficiently using a sliding window technique.
  4. For each valid pair of last two digits, calculate the number of subsequences in O(1). This is determined by the number of digits to the left of the current digit in the string (which acts as the second-last digit of the subsequence).

This approach effectively reduces the time complexity to O(n), where n is the length of the string.

class Solution{

	public:
	const int mod = 1e9+7;
	
	long long helper(string &s, int N, int i,int rem, vector<vector<int>> &dp){
	    if(i == s.length())return 0;
	    if(dp[i][rem]!=-1)return dp[i][rem];
	    long long curr_rem = (rem*10 + (s[i]-'0'))%N;
	    long long take = 0, not_take = 0;
	    if(curr_rem == 0)take = 1+helper(s,N,i+1,curr_rem,dp);
	    else take = helper(s,N,i+1,curr_rem,dp);
	    not_take = helper(s,N,i+1,rem,dp);
	    return dp[i][rem] = (take+not_take)%mod;
	}
	
	int countDivisibleSubseq(string s, int N)
	{
	    vector<vector<int>>dp(s.length(),vector<int>(N,-1));
	    return helper(s,N,0,0,dp);
	}
	  
};
Practice Here on GFG
Solution of the problem asked in the interview. In case of any error email me on raunit@raunit.dev
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;


long long power(int i) {
    long long result = 1;
    long long base = 2;

    while (i > 0) {
        if (i % 2 == 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        i /= 2;
    }

    return result;
}

int countDivisibleSubsequences(string s) {
    int n = s.size();
    vector<int> countRightEven(n + 1, 0), countRightOdd(n + 1, 0);
    long long result = 0;

    for (int i = n - 1; i >= 0; i--) {
        countRightEven[i] = countRightEven[i + 1];
        countRightOdd[i] = countRightOdd[i + 1];
        if (s[i] == '0' || s[i] == '4' || s[i] == '8') countRightEven[i]++;
        if (s[i] == '2' || s[i] == '6') countRightOdd[i]++;
    }

    for (int i = 0; i < n; i++) {
        if (s[i] < '0' || s[i] > '9') continue;

        if ((s[i] - '0') % 2 == 0) { 
            long long res = power(i);
            res *= countRightEven[i+1];
            result += res % MOD;
            if((s[i]-'0')%4 == 0)result++;
            result%=MOD;
        } else {
            long long res = power(i);
            res *= countRightOdd[i+1];
            result += res % MOD;
            result %=MOD;
        }
    }

    return result;
}

int main() {
    string s;
    // cout << "Enter the string: ";
    cin >> s;

    cout 
    // << "Number of subsequences divisible by 4: " 
         << countDivisibleSubsequences(s) << endl;

    return 0;
}

Tested the Above Code for Large Input on GFG Problem

Input:

37459827897589475823423232345234294892304823948231489205884957985735723473489571847125897342589127523591751345
4
    

Output:

822736887
    

Output on GFG:

822736887
    

Explanation of the Solution

The given code solves the problem of counting subsequences divisible by a number N from the string s using dynamic programming (DP).

Key Concepts:

  • The goal is to find subsequences of the string whose integer value is divisible by N.
  • The code uses a recursive approach with memoization (DP) to efficiently calculate the number of valid subsequences.

Detailed Explanation:

  1. The recursive function `helper` takes four arguments:
    • `s` - The input string representing the number.
    • `N` - The number for which subsequences should be divisible.
    • `i` - The current index in the string.
    • `rem` - The current remainder when the subsequence is divided by N.
  2. The function performs the following logic:
    • If the current index (`i`) reaches the end of the string, return 0 because no more subsequences can be formed.
    • If the result for the current state (`i`, `rem`) is already calculated (memoized), return it from `dp[i][rem]`.
    • For each digit in the string, the current remainder `curr_rem` is calculated by adding the current digit to the previous remainder (multiplied by 10) modulo N.
    • If the remainder `curr_rem` is divisible by N (i.e., `curr_rem == 0`), the subsequence is valid, and we consider it by taking the current digit in the subsequence (add 1 to the count). Otherwise, we skip the current digit.
    • In both cases (taking or not taking the digit), the function recursively calculates the subsequences for the remaining string.
    • The result is memoized to avoid recalculating the same state multiple times.
  3. The final result is returned from the `countDivisibleSubseq` function, which initializes the DP table and starts the recursive calculation from the first index with remainder 0.

Time Complexity: The solution has a time complexity of O(n * N), where n is the length of the string, and N is the number for divisibility checks.

Space Complexity: The space complexity is O(n * N) due to the DP table storing results for each index and remainder combination.

Tagsc++interviewsalesforcegfgdp
raunit-picture
raunit

Technical Writer at CodingKaro

Share this on
Other Blogs in Coding