Given a string consisting of integers 0 to 9. The task is to count the number of substrings which when converted into integer are divisible by 4. Substring may contain leading zeroes.
Examples:
Input : "124" Output : 4 Substrings divisible by 4 are "12", "4", "24", "124" . Input : "04" Output : 3 Substring divisible by 4 are "0", "4", "04" .
Brute Force Approach:
- Initialize a count variable to 0.
- Generate all possible substrings of the given string using nested loops.
- Convert each substring to an integer using the stoi() function.
- Check if the integer is divisible by 4 using the % operator.
- If it is, then increment the count.
- Return the count.
Below is the implementation of above approach .
C++
#include <bits/stdc++.h>using namespace std;int countDivisbleby4(char s[]){ int n = strlen(s); int count = 0; for (int i = 0; i < n; i++) { for (int j = 1; j <= n - i; j++) { string sub = string(s).substr(i, j); int num = stoi(sub); if (num % 4 == 0) { count++; } } } return count;}int main(){ char s[] = "04"; cout << countDivisbleby4(s); return 0;} |
Java
public class SubstringDivisibleBy4 { public static int countDivisibleby4(String s) { int n = s.length(); int count = 0; // Loop through all possible substrings of s for (int i = 0; i < n; i++) { for (int j = 1; j <= n - i; j++) { // Get the substring and convert it to an integer String sub = s.substring(i, i + j); try { int num = Integer.parseInt(sub); // If the substring is divisible by 4, increment the count if (num % 4 == 0) { count++; } } catch (NumberFormatException e) { // If the substring is not a valid integer, skip it continue; } } } return count; } // Test the function with a sample input public static void main(String[] args) { String s = "04"; System.out.println(countDivisibleby4(s)); }} |
Python3
# Function to count the number of substrings that are divisible by 4def countDivisbleby4(s): n = len(s) count = 0 # Loop through all possible substrings of s for i in range(n): for j in range(1, n - i + 1): # Get the substring and convert it to an integer sub = s[i:i+j] num = int(sub) # If the substring is divisible by 4, increment the count if num % 4 == 0: count += 1 return count# Test the function with a sample inputs = "04"print(countDivisbleby4(s)) |
C#
using System;class Program{ static int CountDivisibleBy4(string s) { int n = s.Length; int count = 0; // Loop through all possible substrings of s for (int i = 0; i < n; i++) { for (int j = 1; j <= n - i; j++) { // Get the substring and convert it to an integer string sub = s.Substring(i, j); int num = int.Parse(sub); // If the substring is divisible by 4, increment the count if (num % 4 == 0) { count++; } } } return count; } static void Main(string[] args) { string s = "04"; Console.WriteLine(CountDivisibleBy4(s)); }} |
Javascript
function countDivisibleby4(s) { let n = s.length; let count = 0; for (let i = 0; i < n; i++) { for (let j = 1; j <= n - i; j++) { let sub = s.substring(i, i + j); let num = parseInt(sub); if (num % 4 == 0) { count++; } } } return count;}let s = "04";console.log(countDivisibleby4(s)); |
Output
3
Time Complexity: O(N^2)
Space Complexity: O(1)
Efficient solution : A number is divisible by 4 if its last two digits are divisible by 4 and single-digit numbers divisible by 4 are 4, 8 and 0. So, to calculate the number of substrings divisible by 4 we first count number of 0’s, 4’s and 8’s in the string. Then, we make all pairs of two consecutive characters and convert it into an integer. After converting it into integer we check that whether it is divisible by 4 or not. If it is divisible by 4 then all such substring ending with this last two characters are divisible by 4. Now, the number of such substrings are basically the index of 1st character of pair. To make it more clear, consider string “14532465” then possible pairs are “14”, “45”, “53”, “32”, “24”, “46”, “65” . In these pairs only “32” and “24” when converted into integer are divisible by 4. Then, substrings ( length >= 2 ) divisible by 4 must end with either “32” or “24” So, number of substrings ending with “32” are “14532”, “4532”, “532”, “32” i.e 4 and index of ‘3’ is also 4 . Similarly, the number of substrings ending with “24” is 5.
Thus we get an O(n) solution. Below is the implementation of this approach .
C++
// C++ program to count number of substrings // divisible by 4. #include <bits/stdc++.h> using namespace std; int countDivisbleby4(char s[]) { int n = strlen(s); // In the first loop we will count number of // 0's, 4's and 8's present in the string int count = 0; for (int i = 0; i < n; ++i) if (s[i] == '4' || s[i] == '8' || s[i] == '0') count++ ; // In second loop we will convert pairs // of two consecutive characters into // integer and store it in variable h . // Then we check whether h is divisible by 4 // or not . If h is divisible we increases // the count with ( i + 1 ) as index of // first character of pair for (int i = 0; i < n - 1; ++i) { int h = ( s[i] - '0' ) * 10 + ( s[i+1] - '0' ); if (h % 4 == 0) count = count + i + 1 ; } return count; } // Driver code to test above function int main() { char s[] = "124"; cout << countDivisbleby4(s); return 0; } |
Java
// Java program to count number of substrings// divisible by 4import java.io.*;class GFG { // Function to count number of substrings // divisible by 4 static int countDivisbleby4(String s) { int n = s.length(); // In the first loop we will count number of // 0's, 4's and 8's present in the string int count = 0; for (int i = 0; i < n; ++i) if (s.charAt(i) == '4' || s.charAt(i) == '8' || s.charAt(i) == '0') count++ ; // In second loop we will convert pairs // of two consecutive characters into // integer and store it in variable h . // Then we check whether h is divisible by 4 // or not . If h is divisible we increases // the count with ( i + 1 ) as index of // first character of pair for (int i = 0; i < n - 1; ++i) { int h = ( s.charAt(i) - '0' ) * 10 + ( s.charAt(i+1) - '0' ); if (h % 4 == 0) count = count + i + 1 ; } return count; } // driver program public static void main (String[] args) { String s = "124"; System.out.println(countDivisbleby4(s)); }}// Contributed by Pramod Kumar |
Python3
# Python3 program to count the number of substrings# divisible by 4.def countDivisbleby4(s): n = len(s) # In the first loop we will count number of # 0's, 4's and 8's present in the string count = 0; for i in range(0,n,1): if (s[i] == '4' or s[i] == '8' or s[i] == '0'): count += 1 # In second loop we will convert pairs # of two consecutive characters into # integer and store it in variable h . # Then we check whether h is divisible by 4 # or not . If h is divisible we increases # the count with ( i + 1 ) as index of # first character of pair for i in range(0,n - 1,1): h = (ord(s[i]) - ord('0')) * 10 + (ord(s[i+1]) - ord('0')) if (h % 4 == 0): count = count + i + 1 return count# Driver code to test above functionif __name__ == '__main__': s = ['1','2','4'] print(countDivisbleby4(s))# This code is contributed by# Surendra_Gangwar |
C#
// C# program to count number of // substrings divisible by 4using System; public class GFG { // Function to count number of // substrings divisible by 4 static int countDivisbleby4(string s) { int n = s.Length; // In the first loop we will count // number of 0's, 4's and 8's present // in the string int count = 0; for (int i = 0; i < n; ++i) if (s[i] == '4' || s[i] == '8' || s[i] == '0') count++ ; // In second loop we will convert pairs // of two consecutive characters into // integer and store it in variable h . // Then we check whether h is divisible // by 4 or not . If h is divisible, we // increases the count with ( i + 1 ) // as index of first character of pair for (int i = 0; i < n - 1; ++i) { int h = (s[i] - '0' ) * 10 + (s[i + 1] - '0' ); if (h % 4 == 0) count = count + i + 1 ; } return count; } // Driver Code public static void Main () { string s = "124"; Console.WriteLine(countDivisbleby4(s)); }}// This code is contributed by Sam007 |
PHP
<?php// PHP program to count number // of substrings divisible by 4.function countDivisbleby4( $s){ $n = strlen($s); // In the first loop we // will count number of // 0's, 4's and 8's present // in the string $count = 0; for($i = 0; $i < $n; ++$i) if ($s[$i] == '4' or $s[$i] == '8' or $s[$i] == '0') $count++ ; // In second loop we will convert pairs // of two consecutive characters into // integer and store it in variable h . // Then we check whether h is divisible by 4 // or not . If h is divisible we increases // the count with ( i + 1 ) as index of // first character of pair for ( $i = 0; $i < $n - 1; ++$i) { $h = ( $s[$i] - '0' ) * 10 + ( $s[$i+1] - '0' ); if ($h % 4 == 0) $count = $count + $i + 1 ; } return $count;} // Driver Code $s = "124"; echo countDivisbleby4($s); // This code is contributed by anuj_67.?> |
Javascript
<script>// Javascript program to count number// of substrings divisible by 4.function countDivisbleby4(s){ let n = s.length; // In the first loop we // will count number of // 0's, 4's and 8's present // in the string let count = 0; for(let i = 0; i < n; ++i) if (s[i] == '4' || s[i] == '8' || s[i] == '0') count++; // In second loop we will convert pairs // of two consecutive characters into // integer and store it in variable h . // Then we check whether h is divisible by 4 // or not . If h is divisible we increases // the count with ( i + 1 ) as index of // first character of pair for(let i = 0; i < n - 1; ++i) { let h = (s[i] - '0') * 10 + (s[i + 1] - '0'); if (h % 4 == 0) count = count + i + 1 ; } return count;}// Driver Codelet s = "124";document.write(countDivisbleby4(s));// This code is contributed by _saurabh_jaiswal. </script> |
Output:
4
Time Complexity: O(n)
Auxiliary Space: O(1)
This article is contributed by Surya Priy. 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 write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
