Given a string of digits “0-9”. The task is to find the number of substrings which are divisible by 8 but not by 3.
Examples :
Input : str = "888"
Output : 5
Substring indexes : (1, 1), (1, 2), (2, 2),
(2, 3), (3, 3).
Input : str = "6564525600"
Output : 15
A number is divisible by 3 if sum of its digits is divisible by 3. And the number is divisible by 8 if last three digits are divisible by 8. Now, the idea is to store the prefix sum of the string i.e. count of prefixes such that sum of the digits of the prefix modulo 3 is either 0, 1, 2.
Next we iterate over the string and for each position i, count the number of substrings ending at i and divisible by 8. From this value, we subtract the number of substrings ending at i and divisible by 3. We define a |S| X 3 size 2D array, |S| is size of string, say dp[i][j]. dp[i][j] can be define as at any index i, number of substring starting from index 0 to index i having output j when digits from index 0 are added upto index i and modulo 3. Therefore 0 <= j <= 2, since modulo 3.
Now, we will iterate over string and check each one digit number, two digit number and three digit number which are divisible by 8. For one digit, just check if character at index is 8 or not. For two digit, check whether it is divisible by 8 and not divisible by 3. For three digit, form the number and check if it is divisible by 8 or not. If the number is divisible then last three digits must be divisible by 8.
So all the substrings ending at this index must be divisible by 8 i.e. (i-3) substrings. But it will also contain those substrings which are divisible by 3, so simply remove them using dp[i][j].
Below is the implementation of the above approach:
C++
// CPP Program to count substrings which are // divisible by 8 but not by 3 #include <bits/stdc++.h> using namespace std; #define MAX 1000 // Returns count of substrings divisible by 8 // but not by 3. int count(char s[], int len) { int cur = 0, dig = 0; int sum[MAX], dp[MAX][3]; memset(sum, 0, sizeof(sum)); memset(dp, 0, sizeof(dp)); dp[0][0] = 1; // Iterating the string. for (int i = 1; i <= len; i++) { dig = int(s[i-1])-48; cur += dig; cur %= 3; sum[i] = cur; // Prefix sum of number of substrings whose // sum of digits modulo 3 is 0, 1, 2. dp[i][0] = dp[i-1][0]; dp[i][1] = dp[i-1][1]; dp[i][2] = dp[i-1][2]; dp[i][sum[i]]++; } int ans = 0, dprev = 0, value = 0, dprev2 = 0; // Iterating the string. for (int i = 1; i <= len; i++) { dig = int(s[i-1])-48; // Since single digit 8 is divisible // by 8 and not by 3. if (dig == 8) ans++; // Taking two digit number. if (i-2 >= 0) { dprev = int(s[i-2])-48; // 10th position value = dprev*10 + dig; // Complete 2 digit // number if ((value%8 == 0) && (value%3 != 0)) ans++; } // Taking 3 digit number. if (i-3 >= 0) { dprev2 = int(s[i-3])-48; // 100th position dprev = int(s[i-2])-48; // 10th position // Complete 3 digit number. value = dprev2*100 + dprev*10 + dig; if (value%8 != 0) continue; // If number formed is divisible by 8 then // last 3 digits are also divisible by 8. // Then all the substring ending at this // index is divisible. ans += (i-2); // But those substring also contain number // which are not divisible by 3 so // remove them. ans -= (dp[i-3][sum[i]]); } } return ans; } // Driven Program int main() { char str[] = "6564525600"; int len = strlen(str); cout << count(str, len) <<endl; return 0; } |
Java
// Java program to count substrings which are// divisible by 8 but not by 3import java.io.*;class GFG { // Function that returns count of substrings divisible by 8 // but not by 3 static int count(String s, int len) { int MAX = 1000; int cur = 0, dig = 0; int[] sum = new int[MAX]; int[][] dp = new int[MAX][3]; dp[0][0] = 1; // Iterating the string. for (int i = 1; i <= len; i++) { dig = (int)(s.charAt(i-1)) - 48; cur += dig; cur %= 3; sum[i] = cur; // Prefix sum of number of substrings whose // sum of digits modulo 3 is 0, 1, 2. dp[i][0] = dp[i-1][0]; dp[i][1] = dp[i-1][1]; dp[i][2] = dp[i-1][2]; dp[i][sum[i]]++; } int ans = 0, dprev = 0, value = 0, dprev2 = 0; // Iterating the string. for (int i = 1; i <= len; i++) { dig = (int)(s.charAt(i-1)) - 48; // Since single digit 8 is divisible // by 8 and not by 3. if (dig == 8) ans++; // Taking two digit number. if (i-2 >= 0) { dprev = (int)(s.charAt(i-2)) - 48; // 10th position value = dprev*10 + dig; // Complete 2 digit // number if ((value%8 == 0) && (value%3 != 0)) ans++; } // Taking 3 digit number. if (i-3 >= 0) { dprev2 = (int)(s.charAt(i-3)) - 48; // 100th position dprev = (int)(s.charAt(i-2)) - 48; // 10th position // Complete 3 digit number. value = dprev2*100 + dprev*10 + dig; if (value%8 != 0) continue; // If number formed is divisible by 8 then // last 3 digits are also divisible by 8. // Then all the substring ending at this // index is divisible. ans += (i-2); // But those substring also contain number // which are not divisible by 3 so // remove them. ans -= (dp[i-3][sum[i]]); } } return ans; } // driver program public static void main (String[] args) { String str = "6564525600"; int len = str.length(); System.out.println(count(str, len)); }}// Contributed by Pramod Kumar |
Python3
# Python3 Program to count substrings # which are divisible by 8 but not by 3 # Returns count of substrings # divisible by 8 but not by 3. def count(s, Len): global MAX cur = 0 dig = 0 Sum = [0] * MAX dp = [[0, 0, 0] for i in range(MAX)] dp[0][0] = 1 # Iterating the string. for i in range(1, Len + 1): dig = int(s[i - 1]) - 48 cur += dig cur %= 3 Sum[i] = cur # Prefix sum of number of substrings # whose sum of digits modulo 3 is # 0, 1, 2. dp[i][0] = dp[i - 1][0] dp[i][1] = dp[i - 1][1] dp[i][2] = dp[i - 1][2] dp[i][Sum[i]] += 1 ans = 0 dprev = 0 value = 0 dprev2 = 0 # Iterating the string. for i in range(1, Len + 1): dig = int(s[i - 1]) - 48 # Since single digit 8 is # divisible by 8 and not by 3. if dig == 8: ans += 1 # Taking two digit number. if i - 2 >= 0: dprev = int(s[i - 2]) - 48 # 10th position value = dprev * 10 + dig # Complete 2 digit # number if (value % 8 == 0) and (value % 3 != 0): ans += 1 # Taking 3 digit number. if i - 3 >= 0: dprev2 = int(s[i - 3]) - 48 # 100th position dprev = int(s[i - 2]) - 48 # 10th position # Complete 3 digit number. value = (dprev2 * 100 + dprev * 10 + dig) if value % 8 != 0: continue # If number formed is divisible by 8 # then last 3 digits are also divisible # by 8. Then all the substring ending # at this index are divisible. ans += (i - 2) # But those substring also contain # number which are not divisible # by 3 so remove them. ans -= (dp[i - 3][Sum[i]]) return ans# Driver Code MAX = 1000Str = "6564525600"Len = len(Str) print(count(Str, Len))# This code is contributed # by PranchalK |
C#
// C# program to count substrings which are// divisible by 8 but not by 3using System;class GFG { // Function that returns count of substrings // divisible by 8 but not by 3 static int count(String s, int len) { int MAX = 1000; int cur = 0, dig = 0; int[] sum = new int[MAX]; int[,] dp = new int[MAX,3]; dp[0, 0] = 1; // Iterating the string. for (int i = 1; i <= len; i++) { dig = (int)(s[i-1]) - 48; cur += dig; cur %= 3; sum[i] = cur; // Prefix sum of number of substrings whose // sum of digits modulo 3 is 0, 1, 2. dp[i, 0] = dp[i-1, 0]; dp[i, 1] = dp[i-1, 1]; dp[i, 2] = dp[i-1, 2]; dp[i, sum[i]]++; } int ans = 0, dprev = 0, value = 0, dprev2 = 0; // Iterating the string. for (int i = 1; i <= len; i++) { dig = (int)(s[i-1]) - 48; // Since single digit 8 is divisible // by 8 and not by 3. if (dig == 8) ans++; // Taking two digit number. if (i-2 >= 0) { dprev = (int)(s[i-2]) - 48; // 10th position value = dprev*10 + dig; // Complete 2 digit number if ((value % 8 == 0) && (value % 3 != 0)) ans++; } // Taking 3 digit number. if (i - 3 >= 0) { dprev2 = (int)(s[i-3]) - 48; // 100th position dprev = (int)(s[i-2]) - 48; // 10th position // Complete 3 digit number. value = dprev2 * 100 + dprev * 10 + dig; if (value % 8 != 0) continue; // If number formed is divisible by 8 then // last 3 digits are also divisible by 8. // Then all the substring ending at this // index is divisible. ans += (i - 2); // But those substring also contain number // which are not divisible by 3 so // remove them. ans -= (dp[i - 3,sum[i]]); } } return ans; } // driver program public static void Main (String[] args) { String str = "6564525600"; int len = str.Length; Console.Write(count(str, len)); }}// This code is contributed by parashar. |
Javascript
<script>// JavaScript Program to count substrings// which are divisible by 8 but not by 3// Returns count of substrings// divisible by 8 but not by 3.let MAX = 1000function count(s, Len){ let cur = 0 let dig = 0 let Sum = new Array(MAX).fill(0) let dp = new Array(MAX); for(let i=0;i<MAX;i++){ dp[i] = [0, 0, 0] } dp[0][0] = 1 // Iterating the string. for(let i=1;i<Len + 1;i++){ dig = s.charCodeAt(i - 1) - '0'.charCodeAt(0) cur += dig cur %= 3 Sum[i] = cur // Prefix sum of number of substrings // whose sum of digits modulo 3 is // 0, 1, 2. dp[i][0] = dp[i - 1][0] dp[i][1] = dp[i - 1][1] dp[i][2] = dp[i - 1][2] dp[i][Sum[i]] += 1 } let ans = 0 let dprev = 0 let value = 0 let dprev2 = 0 // Iterating the string. for(let i=1;i<Len + 1;i++){ dig = s.charCodeAt(i - 1) - '0'.charCodeAt(0) // Since single digit 8 is // divisible by 8 and not by 3. if(dig == 8) ans += 1 // Taking two digit number. if(i - 2 >= 0){ dprev = s.charCodeAt(i - 2) - '0'.charCodeAt(0) // 10th position value = dprev * 10 + dig // Complete 2 digit // number if ((value % 8 == 0) && (value % 3 != 0)) ans += 1 } // Taking 3 digit number. if(i - 3 >= 0){ dprev2 = s.charCodeAt(i - 3) - '0'.charCodeAt(0) // 100th position dprev = s.charCodeAt(i - 2) - '0'.charCodeAt(0) // 10th position // Complete 3 digit number. value = (dprev2 * 100 + dprev * 10 + dig) if(value % 8 != 0) continue // If number formed is divisible by 8 // then last 3 digits are also divisible // by 8. Then all the substring ending // at this index are divisible. ans += (i - 2) // But those substring also contain // number which are not divisible // by 3 so remove them. ans -= (dp[i - 3][Sum[i]]) } } return ans}// Driver Codelet Str = "6564525600"let Len = Str.lengthdocument.write(count(Str, Len))// This code is contributed by shinjanpatra</script> |
Output
15
Time Complexity: O(len), Where len is the length of string.
Auxiliary Space: O(MAX), Where MAX is the defined constant.
This article is contributed by Anuj Chauhan. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks. Please
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
