Number of substrings in a string of integers that are divisible by 4

In this article, we have explored algorithms to find the Number of substrings in a string of integers that are divisible by 4.

Table of contents:

1. Problem Statement
2. Brute Force Approach
3. Efficient Approach

Problem Statement

Input : A String of integers(0 to 9),may contain leading zeroes
Output : Number of substrings that are divisible by 4

Example 1:

Input : "480"
Output : 6
Substrings divisible by 4 are "4","8","0","48","80" and "480"

Example 2:

Input : "043"
Output : 3
Substrings divisible by 4 are "0","04" and "4"

Method 1 (Brute Force Technique)

You can consider all the substrings and convert each substring to a number and then check whether that number is divisble by 4 or not,one by one,and count all such number.

Implementaion of above approach is given below.

Implementation 1 (Brute Force Technique) (C++)

#include<bits/stdc++.h>
using namespace std;

//To calculate all substrings of given string and store it in a vector
vector<string> Substring( string s )
{
    vector<string> ans;    //vector for storing substrings
    int i,j;
    
    for(i=0;i<s.length();i++)
    {
        for(j=1;j<=(s.length()-i);j++)
        {
            ans.push_back(s.substr(i,j));
        }
    }
    
    return ans;
}

//To return count of all substrings that are divisible by 4
int divisibleby4(vector<string> ans)
{
    int count=0,num;
    
    for(int i=0;i<ans.size();i++)
    {
        //stoi() is a inbuilt function that converts string (given 
        //in parameter) to integer
        
        num=stoi(ans[i]);
        
        if(num%4==0)
            count++;
    }
    
    return count;
}

//main
int main()
{
    string s;
    
    cin>>s;
    
    vector<string> ans;
    int count;
    
    ans=Substring(s);
    
    count = divisibleby4(ans);
    
    cout<<count<<"\n";
    
    return 0;
}

Input 1

480

Output 1

 6

Complexity Analysis of implementation 1

Time Complexity:O(n^3)
Space Complexity:O(n^2)

Time Complexity is O(n^3) because three nested loops are running for finding all substrings.(Note:substr() also takes linear time to return required substring )

Space Complexity is O(n^2) because for each string,there are n*(n+1)/2 non-empty substrings.Everytime the vector size will be of n*(n+1)/2.Thus Space Complexity is O(n^2)

Surely,this method is not an efficient method.So let's discuss about the efficient method which can solve the problem in O(n) time complexity and O(1) space complexity....

Method 2 (Efficient Approach)

To solve this problem efficiently i.e. in O(n) time,we need to know the condition of divisibility by 4.

Base Idea : "" A number is said to be divisible by 4,if its last two digits (combined) are divisible by 4.In case of single digit number,only 0,4 and 8 are divisible by 4.""

For Example : 480 is divisible by 4 because 80 (last two digits combined) is divisible by 4 and 455 is not( why? )

So,we will use this basic number theory concept to solve this problem!!

Now,we know that in a given string,the substrings that are divisble by 4 can be of unit length or more than unit length also.

For unit length substring,we know that only '0','4' and '8' are divisibe by 4.Thus,by counting all '0','4' and '8',we will get one part of our answer.

Now,for counting all the remaining substring,we will deploy our base idea.

Starting from the first character, we will consider pairs of consecutive characters one by one.We will convert each pair into a number and check if this number is divisible by 4 or not. If this number is divisble by 4,then all the substrings that are ending with this pair will be divisible by 4 and number of all substrings that are ending with the pair will be equal to index (1 based ) of first character of pair.

I hope you have understood the approach for solving this problem,if not read once again the above para.

Now,consider an example for better understanding

For Example:
Input : "41233882"

First count all the '0','4' and '8' in the string.Here '0' is not present at all,'4' is present once and '8' is present twice in the string.
Count_unit = 3

Now consider all pair of consecutive characters:

                "41","12","23","33","38","88","82"

Out of these only "12" and "88" are divisible by 4.So all the substrings
that are ending with "12" and "88" are divisible by 4.

with "12" : "412" and "12" are ending ,and
with "88" : "4123388","123388", "23388","3388","388","88" are ending.

Considering 1-based indexing, index of '1' ( first character of pair "12") is 2 and index of '8' ( first character of pair "88") is 6.
Count_multidigit = 8

Final Answer : 11

Implementation 2 (C++)

#include<bits/stdc++.h>
using namespace std;

//for counting all substrings that are of unit length and divisible by 4
int unit_digit(string s)
{
    int count=0;
    
    for(int i=0;i<s.length();i++)
    {    
        if(s[i]=='0' || s[i]=='4' || s[i]=='8') 
            count++;
    }
    
    return count;        
}

//for counting all the remaining multidigit substrings that are divisble by 4
int multi_digit(string s)
{
    int count=0;
    int num;
    
    for(int i=0;i<s.length()-1;i++)
    {
        //converting pair of character into a number
        num=(s[i]-'0')*10+(s[i+1]-'0');  
        
        if(num%4==0)
            count = count + (i+1);
    }
    return count;
}

//main
int main()
{
    string s;
    cin>>s;
    
    int cnt_unit = unit_digit(s);
    int cnt_multidigit = multi_digit(s);
    int answer=( cnt_unit + cnt_multidigit );
    
    cout<<answer<<endl;
   
    return 0;
}

Input 2

41233882

Output 2

11

Complexity Analysis of implementation 2

Time complexity:O(n)
Space complexity:O(1)

Time Complexity is O(n) because only a single traversal of string is required in both the functions.

Space Complexity is O(1) because every variable declared above require constant space and do not depends on the input size.

That's all.I Hope you find it informative!!!