Counting divisible Substrings

[PrashantVIT1]

Description

|| 8th Mar 2022 || HackWithInfy || Infosys ||

You are given a string Str of length N. Each character of the string is a base 10 digit.

Your task is to find the total number of substrings of Str such that the number denoted by the string Str[i...j] is divisible by 6. Since that result can be a very large return it is modulo 10^9+7.

Notes:
* It is given that a number denoted by Str[i..j] can have leading Zeroes.

Input Format
The first line contains an integer, N, denoting the length of the given string.
The next line contains a string, Str, denoting the given string.

Constrains
1 <= N <= 10^5
1 <= len(Str) <= 10^5


    

        
Sample Input
        
Sample Output
        
Explanation
    
    

        
3
328
        
0
        
No substring is divisible by 6
    
    

        
3
318
        
2
        
"18","318" divisible by 6
    
        

        
4
6151
        
1
        
"6" divisible by 6
    

Domain

Competitive Programming

Type of Contribution

Addition

Code of Conduct

• I follow Contributing Guidelines & Code of conduct of LearnCPP.

[github-actions]

Hello @PrashantVIT1, thanks for creating your first issue at LearnCPP, hope you followed the guidelines.

[PrashantVIT1]

/assign

[github-actions]

This issue has been assigned to PrashantVIT1!
It will become unassigned if it is not closed within 12 days. A maintainer can also add the pinned label to prevent it from being unassigned.

[PrashantVIT1]

I have created another issue that has not been merged yet

[github-actions]

The issue is already assigned!
Please find/create a new issue to contribute to.
You can safely disregard the failed workflow notification for this issue. ❌