Get this book -> Problems on Array: For Interviews and Competitive Programming

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.**

- For one digit number(that we get on fetching from str[], simply check

## 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.