Even Substring Count

Difficulty Level Easy
Frequently asked in Coursera Deutsche Bank OYO Rooms Yahoo Yandex Zoho
StringViews 3431

Problem Statement

In the “Even Substring Count” problem we have given an input string which is formed by digits. Write a program or code to find the count of substrings which when converting into integer form even.

Input Format

The first and only one line containing a string “s”.

Output Format

The first line contains an integer value that represents the number of substrings of “s” which when converting into integer form even.

Constraints

  • 1<=|s|<=10^6
  • s[i] is in the range from 0 to 9

Example

1234
6

Explanation: Here we simply check the position of the even digit and add the position of this digit(1-base indexing) into the answer. Like here the position of ‘2’ is 2 so we add 2 to our answer. Now moving ahead and see the next digit is ‘4’ and we add 4 to our answer. So, we got our answer which is 6. And if we check manually  2, 4, 12, 34, 234, 1234 are the substrings that are even and their_count is also equal to 6.

Algorithm for Even Substring Count

1. Declare one variable ans and set it to zero.

2. Start traversing from the beginning of the string and check for the digit.

3. If the digit is even then add the position(1-based indexing) of this number into the answer.

4. Print ans which containing the count of the substrings.

Implementation

C++ Program for Even Substring Count

#include <bits/stdc++.h>

using namespace std;

int main()
{
   string s;
   cin>>s;
   int n=s.length();
   int ans=0;
   for(int i=0;i<n;i++)
   {
       if((s[i]-'0')%2==0)
       {
           ans+=(i+1);
       }
   }
   cout<<ans<<endl;
   return 0;
}

Java Program for Even Substring Count

import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
    int n = s.length();
                int ans=0;
                for(int i=0;i<n;i++)
                {
                    int x = s.charAt(i)-48;
                    if(x%2==0)
                    {
                        ans+=(i+1);
                    }
                }ven dig
                System.out.println(ans);
  } 
} 

213578
7

Complexity Analysis for Even Substring Count

Time Complexity

O(n) where n is the size of the given string. Here we simply traverse the given string and add the index of the even digit into our answer.

Space Complexity

O(1) because we don’t use any auxiliary space here. Here we only declare one variable to store the answer and print it.

Translate »