Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

We need to find total number of substrings that are divisible by 8 but not 3 in the given string. For example, consider the string "356", this contains 1 substring that is divisible by 8 but not 3 i.e, 56, note that 3, 5, 6, 35, 356 aren't divisible by 8 and hence don't contribute towards the solution.

Before we start, recall:

A number x is said to be divisible by y is x % y == 0
A number is divisible by 3 if sum of its digit is divisible by 3
A number is divisible by 8 if its last three digits are divisible by 8

We have solved this problem using Dynamic Programming in linear time O(N). The brute force approach takes O(N^2) time.

Method 1

A simple approach will suggest to count the number of substrings divisible by 8 and subtract those divisible by 24 from it ( Since if a number is divisible by 24, it implies it is divisible by both 8 and 3).

PseudoCode to count all substrings divisible by 'k'

1. for (int i = 0; i < len; i++)
2.     for (int j = i; j < len; j++) 
3.         n = n * 10 + (str[j] - '0')
4.         if(n % k == 0)
5.             count ++
6.         else
7.             continue

Here we are simply iterating over the string and selecting every substring that starts from index 'i' and are checking if it divides 'k' (leaves 0 as remainder). Also, we are subsequently adding this substring to the previous ones( which is again compared for remainder on dividing with 'k') and hence this procedure makes sure that we take in account every possible substring.
Now, if we could count the number of substrings divisible by k, we can surely found that of 8 and 24, (by replacing k with 8 and 24)

Code

#include <bits/stdc++.h> 
using namespace std; 

int no_of_substr(string str, int len, int k) 
{ 
    int count = 0; 
    // iterate over the string 
    for (int i = 0; i < len; i++) { 
        int n = 0; 
        // consider every substring starting from index 'i'
        for (int j = i; j < len; j++) { 
            n = n * 10 + (str[j] - '0'); 
            // if substring is divisible by k, increase the counter
            if (n % k == 0) 
                count++; 
        } 
    } 
    return count; 
} 
  
int main() 
{ 
    string str;
    int len;
    cout << "Enter the string: ";
    cin >> str;
    len = str.length(); 
    cout << "Desired Count: " << no_of_substr(str, len, 8) - no_of_substr(str, len, 24); 
  
    return 0; 
}

Sample I/O

Enter the string: 1892456
Desired count: 6

Here, the entered string is "1892456", note that substrings divisible by 8 but not 3 are "8", "56", "2456", "92456", "892456", "1892456" which count to 6 and that is what we got as answer. So, this works fine.

But take a note that here the time complexity is O(N^2), which we would like to improve.

Method 2

Dynamic Programming here comes to our rescue, below algorithm effectively reduces the time complexity to O(n).

Dynamic Programming Algorithm

Define an array dp[1000][3] such that its every element dp[i][j] stores the count of substrings ending at index i and gives j as remainder when divided by 3.

dp[i][j] = number of substrings ending at index i and 
           gives j as remainder when divided by 3

Initialize dp[0][0] with 1 and while iterating the string str[]
- Fetch the recent digit (str[i-1])
- Compute and Store str[i - 1] % 3 in rem[i]
- Copy the values of dp[i - 1][j] to dp[i][j] where j = 0, 1, 2
- Increment dp[i][rem[i]] by 1 as we get rem[i] with the recent digit we encountered
Initialize res = 0 (that will store the result)
While iterating over the string, check the numbers for divisiblity by 8
- For one digit number(that we get on fetching from str[], simply check if it 8 and increment res, if yes
- For two digit number**(that would be formed using the previous digit and current digit as previous_digit * 10+current_digit)**, check if this number is divisible by 8 and increment the res, if yes
- For three digit number (i.e, prev_previous_digit * 100 + previous_digit * 10 + current_digit), check if it is divisible by 8. If yes, then all the substrings ending at this index will be divisible by 8. (Consider a number "154256", here "256" is divisible by 8 and this implies "154256", "54256", "4256", "256" are also divisible by 8. This hints us to note that under above conditions, i-2 substrings will be divisible by 8. But herein, we have not excluded those substrings that are divisible by 3. Therefore, we will subtract dp[i - 3][rem[i]] from res.

Learn to solve other Algorithmic problems using Dynamic Programming

Code

#include <bits/stdc++.h> 
using namespace std; 
int no_of_substring(char str[], int n) 
{ 
    int current_digit = 0, digit = 0; 
    int rem[1000], dp[1000][3]; 
    // initializing both arrays with 0
    memset(rem, 0, sizeof(rem)); 
    memset(dp, 0, sizeof(dp)); 
    dp[0][0] = 1; 
    for (int i = 1; i <= n; i++) 
    { 
        digit = int(str[i-1])-'0'; 
        current_digit += digit; 
        current_digit %= 3;  
        rem[i] = current_digit; 
        dp[i][0] = dp[i-1][0]; 
        dp[i][1] = dp[i-1][1]; 
        dp[i][2] = dp[i-1][2]; 
        dp[i][rem[i]]++; 
    } 
    int res = 0, previous_digit = 0, value = 0, prev_previous_digit = 0; 
    for (int i = 1; i <= n; i++) 
    { 
        digit = int(str[i-1])-'0'; 
        if (digit == 8) 
            res++; 
        if (i-2 >= 0) 
        { 
            previous_digit = int(str[i-2])-'0';  
            value = previous_digit*10 + digit;                   
            if ((value%8 == 0) && (value%3 != 0)) 
                res++; 
        } 
        if (i-3 >= 0) 
        { 
            prev_previous_digit = int(str[i-3])-'0'; 
            previous_digit  = int(str[i-2])-'0';  
            value = prev_previous_digit*100 + previous_digit*10 + digit; 
            if (value%8 != 0) 
                continue; 
            res += (i-2); 
            res -= (dp[i-3][rem[i]]); 
        } 
    } 
    return res; 
} 
int main() 
{ 
    int n;
    cout << "\n Enter the length of string: ";
    cin >> n;
    char str[n]; 
    cout<<"\n Enter the string: ";
    for(int i = 0; i < n; i++)
    {
    	cin>>str[i];
	}
    cout << "\n Number of desired substrings: " << no_of_substring(str, n) <<endl; 
    return 0; 
}

Sample I/O

Enter the length of string: 3
Enter the string: 356
Number of desired substrings: 1

Now, in this case we have string as "356"
and the dynamic programming table looks like:

0	1	2
1	0	0
0	0	0
0	0	0
0	0	0

in the next iteration (i = 1), initialize dp[i][j] with dp[i - 1][j] but since 3 % 3 ==0, rem[1] = 0 and we increament dp[1][0] by 1

0	1	2
1	0	0
2	0	0
0	0	0
0	0	0

in the next iteration (i = 2), initialize dp[i][j] with dp[i - 1][j] but since 5 % 3 == 2, rem[2] = 0 and we increament dp[2][2] by 1

0	1	2
1	0	0
2	0	0
2	0	1
0	0	0

in the next iteration (i = 3), initialize dp[i][j] with dp[i - 1][j] but since 8 % 3 == 2, rem[2] = 0 and we increament dp[3][2] by 1

0	1	2
1	0	0
2	0	0
2	0	1
2	0	2

which is our final table.
Now when we will iterate over the string,
when i = 1: we calculate 3 % 8 which is not 0, therefore, res remains 0

when i = 2: we calculate 5 % 8 which is not 0, therefore, res remains 0
also, we here check if 35 % 8 is 0, which is not the case. Therefore, res remains 0

when i = 3: we calculate 6 % 8 which is not 0, therefore, res remains 0
also, we here check if 56 % 8 is 0, which the case. Therefore, res += 1
now, we check if 356 % 8 is 0, which is not so. Hence, we get the result as 1

Complexity

Time Complextity = O(n)
Space Complexity = O(1)

With this article at OpenGenus, you must have the complete idea of finding the number of substrings divisible by 8 but not 3 using Dynamic Programming. Enjoy.