Number of even substrings in a string of digits
Given a string of digits 0 – 9. The task is to count a number of substrings which when converting into integer form an even number.
Examples :
Input : str = "1234".
Output : 6
"2", "4", "12", "34", "234", "1234"
are 6 substring which are even.
Input : str = "154".
Output : 3
Input : str = "15".
Output : 0
For a number to be even, the substring must end with an even digit. We find all the even digits in the string and for each even digit, count the number of substrings ending with it. Now, observe that the number of substrings will be an index of that even digit plus one.
Implementation:
C++
// C++ program to count number of substring // which are even integer in a string of digits. #include<bits/stdc++.h> using namespace std; // Return the even number substrings. int evenNumSubstring( char str[]) { int len = strlen (str); int count = 0; for ( int i = 0; i < len; i++) { int temp = str[i] - '0' ; // If current digit is even, add // count of substrings ending with // it. The count is (i+1) if (temp % 2 == 0) count += (i + 1); } return count; } // Driven Program int main() { char str[] = "1234" ; cout << evenNumSubstring(str) << endl; return 0; } |
Java
// Java program to count number of // substring which are even integer // in a string of digits. public class GFG { // Return the even number substrings. static int evenNumSubstring(String str) { int len = str.length(); int count = 0 ; for ( int i = 0 ; i < len; i++) { int temp = str.charAt(i) - '0' ; // If current digit is even, add // count of substrings ending with // it. The count is (i+1) if (temp % 2 == 0 ) count += (i + 1 ); } return count; } public static void main(String args[]) { String str= "1234" ; System.out.println(evenNumSubstring(str)); } } // This code is contributed by Sam007. |
Python3
# Python 3 program to count number of substring # which are even integer in a string of digits. # Return the even number substrings. def evenNumSubstring( str ): length = len ( str ) count = 0 for i in range ( 0 ,length, 1 ): temp = ord ( str [i]) - ord ( '0' ) # If current digit is even, add # count of substrings ending with # it. The count is (i+1) if (temp % 2 = = 0 ): count + = (i + 1 ) return count # Driven Program if __name__ = = '__main__' : str = [ '1' , '2' , '3' , '4' ] print (evenNumSubstring( str )) # This code is contributed by # Surendra_Gangwar |
C#
// C# program to count number of // substring which are even integer // in a string of digits. using System; public class GFG { // Return the even number substrings. static int evenNumSubstring( string str) { int len = str.Length; int count = 0; for ( int i = 0; i < len; i++) { int temp = str[i] - '0' ; // If current digit is even, // add count of substrings // ending with it. The count // is (i+1) if (temp % 2 == 0) count += (i + 1); } return count; } // Driver code public static void Main() { string str= "1234" ; Console.Write( evenNumSubstring(str)); } } // This code is contributed by Sam007. |
Javascript
<script> // Javascript program to count number of // substring which are even integer // in a string of digits. // Return the even number substrings. function evenNumSubstring(str) { let len = str.length; let count = 0; for (let i = 0; i < len; i++) { let temp = str[i] - '0' ; // If current digit is even, // add count of substrings // ending with it. The count // is (i+1) if (temp % 2 == 0) count += (i + 1); } return count; } let str= "1234" ; document.write(evenNumSubstring(str)); </script> |
PHP
<?php // PHP program to count number // of substring which are even // integer in a string of digits. // Return the even number substrings. function evenNumSubstring( $str ) { $len = strlen ( $str ); $count = 0; for ( $i = 0; $i < $len ; $i ++) { $temp = $str [ $i ] - '0' ; // If current digit is even, add // count of substrings ending with // it. The count is (i+1) if ( $temp % 2 == 0) $count += ( $i + 1); } return $count ; } // Driver Code $str = "1234" ; echo evenNumSubstring( $str ), "\n" ; // This code is contributed by jit_t ?> |
6
Time Complexity: O(length of string).
This article is contributed by Anuj Chauhan.
Count Even and Odd Digits:
Approach:
Initialize variables e and o to 0, which will be used to count the number of even and odd digits in the string.
Loop through each character in the string s, and for each character:
a. Convert the character to an integer and check if it is even by taking its modulus with 2. If it is even, increment e by 1, otherwise increment o by 1.
Calculate the number of even and odd substrings using the formula (n*(n+1))/2, where n is the number of even or odd prefixes. This formula is derived from the fact that the number of substrings that can be formed from a string of length n is (n*(n+1))/2.
Add the number of even and odd substrings to get the total number of even substrings.
Return the total number of even substrings.
C++
#include <iostream> #include <string> using namespace std; // Function to count the number of substrings with an even number of even digits int count_even_substrings(string s) { int n = s.length(); // Get the length of the input string int e = 0; // Initialize a counter for even digits // Loop through each character in the string for ( char c : s) { // Check if the character is an even digit (0, 2, 4, 6, or 8) if ((c - '0' ) % 2 == 0) { e++; // Increment the even digit counter } } int o = n - e; // Calculate the number of odd digits // Calculate the total number of substrings with an even number of even digits // by summing the combinations of substrings with even and odd digits return (e * (e + 1) / 2) + (o * (o + 1) / 2); } int main() { string s = "1234" ; cout << count_even_substrings(s) << endl; // Output: 6 return 0; } |
Java
import java.util.Scanner; public class Main { // Function to count the number of substrings with an even number of even digits static int countEvenSubstrings(String s) { int n = s.length(); // Get the length of the input string int e = 0 ; // Initialize a counter for even digits // Loop through each character in the string for ( char c : s.toCharArray()) { // Check if the character is an even digit (0, 2, 4, 6, or 8) if ((c - '0' ) % 2 == 0 ) { e++; // Increment the even digit counter } } int o = n - e; // Calculate the number of odd digits // Calculate the total number of substrings with an even number of even digits // by summing the combinations of substrings with even and odd digits return (e * (e + 1 ) / 2 ) + (o * (o + 1 ) / 2 ); } public static void main(String[] args) { String s = "1234" ; System.out.println(countEvenSubstrings(s)); // Output: 6 } } |
Python3
def count_even_substrings(s): n = len (s) e = sum ( 1 for c in s if int (c) % 2 = = 0 ) o = n - e return (e * (e + 1 ) / / 2 ) + (o * (o + 1 ) / / 2 ) s = "1234" print (count_even_substrings(s)) # Output: 6 |
C#
using System; class Program { // Function to count the number of substrings with an // even number of even digits static int CountEvenSubstrings( string s) { int n = s.Length; // Get the length of the input // string int e = 0; // Initialize a counter for even digits // Loop through each character in the string foreach ( char c in s) { // Check if the character is an even digit (0, // 2, 4, 6, or 8) if ((c - '0' ) % 2 == 0) { e++; // Increment the even digit counter } } int o = n - e; // Calculate the number of odd digits // Calculate the total number of substrings with an // even number of even digits by summing the // combinations of substrings with even and odd // digits return (e * (e + 1) / 2) + (o * (o + 1) / 2); } static void Main() { string s = "1234" ; Console.WriteLine( CountEvenSubstrings(s)); // Output: 6 } } |
Javascript
function count_even_substrings(s) { // Get the length of the string let n = s.length; // Count the number of even digits in the string let e = [...s].filter(c => parseInt(c) % 2 == 0).length; // Calculate the number of odd digits in the string let o = n - e; // Return the sum of the number of substrings with an even number of even digits // and the number of substrings with an odd number of even digits return (e*(e+1)/2) + (o*(o+1)/2); } // Example usage let s = "1234" ; console.log(count_even_substrings(s)); // Output: 6 |
6
The time complexity of this algorithm is O(n), where n is the length of the input string s. This is because the algorithm iterates through the input string once to count the number of even and odd digits, and then performs two constant-time calculations to determine the number of even and odd substrings. The dominant operation in this algorithm is the iteration through the input string, which takes O(n) time.
The auxiliary space of this algorithm is O(1), because the algorithm only uses a constant amount of additional space to store the counts of even and odd digits. The amount of additional space used does not depend on the length of the input string. Therefore, the space complexity of this algorithm is constant.
Contact Us