Given a very large number N, we need to count the total ways such that if we divide the number into two parts a and b, the first part a can be obtained by integral division of second b by some power p of 10 and p>=0. 1 <= No of digits in N <= 
.
Examples:
Input : 220 Output : 1 220 can be divided as a = 2 and b = 20 such that for p = 1, b/10 = a. Input : 1111 Output : 2 We get answer 2 because we need to consider integral division. Let's consider the first partition a = 1, b = 111. for p = 2, b/pow(10,p) = a thus this is a valid partition. now a = 11, b = 11. for p = 0, b/pow(10,p) = a thus this too is a valid combination. Input : 2202200 Output : 2 for a = 2 b = 202200, p = 5 and a = 220, b = 2200, p = 1
Since the number can be very large to be contained even in a long long int we will store it as a string. According to the conditions mentioned in the problem, division is the floor function. A simple and inefficient approach will be to divide the string into two substrings then convert those to integer and perform division. An efficient method to do it will be to use the string compare function to match the most significant digits of the two strings and ignore the rest( floor function).
Below is the implementation of this idea :
C++
#include <bits/stdc++.h>using namespace std;// c++ function to count ways to divide a// string in two parts a and b such that// b/pow(10, p) == aint calculate(string N){ int len = N.length(); int l = (len) / 2; int count = 0; for (int i = 1; i <= l; i++) { // substring representing int a string s = N.substr(0, i); // no of digits in a int l1 = s.length(); // consider only most significant // l1 characters of remaining string // for int b string t = N.substr(i, l1); // if any of a or b contains leading 0s // discard this combination if (s[0] == '0' || t[0] == '0') continue; // if both are equal if (s.compare(t) == 0) count++; } return count;}// driver function to test above functionint main(){ string N = "2202200"; cout << calculate(N); return 0;} |
Java
// Java program to count ways to divide a// String in two parts a and b such that// b/pow(10, p) == aimport java.util.*;class GFG{static int calculate(String N){ int len = N.length(); int l = (len) / 2; int count = 0; for (int i = 1; i <= l; i++) { // subString representing int a String s = N.substring(0, i); // no of digits in a int l1 = s.length(); // consider only most significant // l1 characters of remaining String // for int b String t = N.substring(i, l1 + i); // if any of a or b contains leading 0s // discard this combination if (s.charAt(0) == '0' || t.charAt(0) == '0') continue; // if both are equal if (s.compareTo(t) == 0) count++; } return count;}// Driver Codepublic static void main(String[] args){ String N = "2202200"; System.out.print(calculate(N));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to count ways to divide# a string in two parts a and b such that# b/pow(10, p) == adef calculate( N ): length = len(N) l = int((length) / 2) count = 0 for i in range(l + 1): print(i) # substring representing int a s = N[0: 0 + i] # no of digits in a l1 = len(s) print(s,l1) # consider only most significant # l1 characters of remaining # string for int b t = N[i: l1 + i] # if any of a or b contains # leading 0s discard this try: if s[0] == '0' or t[0] == '0': continue except: continue # if both are equal if s == t: count+=1 print(i,N[i],count) return count # driver code to test above functionN = str("2202200")print(calculate(N))# This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program to count ways to divide a// String in two parts a and b such that// b/pow(10, p) == ausing System;class GFG{static int calculate(String N){ int len = N.Length; int l = (len) / 2; int count = 0; for (int i = 1; i <= l; i++) { // subString representing int a String s = N.Substring(0, i); // no of digits in a int l1 = s.Length; // consider only most significant // l1 characters of remaining String // for int b String t = N.Substring(i, l1); // if any of a or b contains leading 0s // discard this combination if (s[0] == '0' || t[0] == '0') continue; // if both are equal if (s.CompareTo(t) == 0) count++; } return count;}// Driver Codepublic static void Main(String[] args){ String N = "2202200"; Console.Write(calculate(N));}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript program to count ways to divide// a string in two parts a and b such that// b/pow(10, p) == afunction calculate( N ){ let len = N.length let l = Math.floor((len) / 2) let count = 0 for(let i = 1; i < l + 1; i++) { // substring representing int a let s = N.substr(0, i) // no of digits in a let l1 = s.length // consider only most significant // l1 characters of remaining // string for int b let t = N.substr(i,l1) // if any of a or b contains // leading 0s discard this if (s[0] == '0' || t[0] == '0'){ continue } // if both are equal if(s === t) count++ } return count} // driver code to test above functionlet N = "2202200"console.log(calculate(N))// This code is contributed by shinjanpatra</script> |
Output
2
Time Complexity: O(n2)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
