Divisible Substrings

Easy
0/40
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in company
HashedIn

Problem statement

You are given a number in the form of a string ‘S’ of length ‘N’ consisting of characters from '0' to '9' (both inclusive) .

You must return the number of substrings that are divisible by 5. Some strings divisible by 5 are ‘5’, ‘370’, and ‘1000’.

Note :

A substring can start with a zero. The given number may also contain leading zeroes.

Example:

‘S'= ‘5203’

Here, four substrings are divisible by 5: ‘5’, ’520’, ‘20’, ‘0’.
Hence the answer is 4.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
First-line contains 'T', denoting the number of Test cases.

For each Test case:

The first line contains an integer ‘N’ denoting the string ‘S’ length.
The second line contains a string ‘S’ of size ‘N’.
Output format : 
Return an integer denoting the total number of substrings whose integral value are divisible by 5.
Note:- 
You don't need to print anything. Just implement the given function.
Constraints : 
1 <= 'T' <= 10
1 <= 'N' <= 10^5
'0' <= 'S[i]' <= '9'


Time Limit: 1 sec
Sample Input 1 :
2
5
35602
3
100
Sample Output 1 :
6
5
Explanation Of Sample Input 1 :
For test case 1:

‘S'= ‘35602’
Here, six substrings are divisible by 5: ‘35’, ’3560’, ‘5’, ‘560’, ‘60’, ‘0’.
Hence the answer is 6.


For test case 2:

‘S'= ‘100’
Here, five substrings are divisible by 5: ‘10’, ’100’, ‘0’, ‘00’, ‘0’.
Hence the answer is 5.
Sample Input 2 :
2
1
9
4
1555
Sample Output 2 :
0
9
Hint

How to check for all substrings ?

Approaches (2)
Brute Force

Approach:-


 

  • Every number whose unit digit is 0 or 5 is divisible by 5. Ex - 5, 75, 60 etc.
  • So, every substring that ends with a ‘0’ or ‘5’ is divisible by 5.
  • The count of all such substrings is our answer.


 

 Algorithm:-

  • Initialize a variable ‘answer’ with 0.
  • for i = 0 to N-1 :
    • for j = i to N-1:
      • If ‘s[j]’ == ‘0’ or ‘s[j]’ == ‘5‘ :
        • ‘answer’ = ‘answer’+1
  • Return ‘answer’.
Time Complexity

O(N^2), where 'N' is the string ‘S' length.

 

We are checking every substring of ‘S’. Hence, overall time complexity is O(N^2).

Space Complexity

O(1).

 

We are using some variables which take constant space.  So the space complexity is O(1).

Code Solution
(100% EXP penalty)
Divisible Substrings
Full screen
Console