Prefix Number <Liv.ai>
Practice
4.3 (7 votes)
Algorithms
Kmp algorithm
Medium
Open
String manipulation
Z algorithm
Z Algorithm
Problem
75% Success 4217 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Given a very large number N, you need to count the total ways such that if we divide the number into two parts a and b then number a can be obtained by integral division of number b by some power p of 10 and \(p \ge 0\).

For example: Let 220 be a number then, if you divide the number into two parts 2 and 20 then, if 20 is divided by \(10^1\) gives the number 2.

Important Notes:
1. You cannot perform any irregular division of the number i.e the original number should be formed after concatenation of the two parts a and b. Example of irregular division is 289 divided as 29 and 8

2. Both the numbers a and b should not contain any leading zeros

3. Integral division of any two numbers \(a,b\) is \(F(a/b)\) where F is the floor function

Input Format
A line that contains a very large number N(string of digits \(0-9\)).

Output Format
Total number of ways to divide the string such that it follows the above constraints.

Input Constraints
\(1 \le |N| \le 10^5\) where |N| is length of the number N

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
13 votes
Tags:
ApprovedHash MapsMediumReadyString ManipulationZ algorithmZ-algorithm
Points:30
5 votes
Tags:
AlgorithmsDynamic ProgrammingMediumReadyZ algorithmZ-algorithm
Points:30
17 votes
Tags:
AlgorithmsApprovedKMP AlgorithmMediumZ algorithmZ-algorithm