Given a large number in string format and we are also given two numbers f and s. We need to divide the large number into two continuous parts such that the first part is divisible by f and the second part is divisible by s.
Examples:
Input: num = “246904096”
f = 12345
s = 1024
Output: Yes
We can divide num into “24690” and “4096”
which are divisible by f and s respectively.
Input : num = “1234”
f = 1
s = 123
Output : No
We can not divide num into two parts under
given constraint.
A simple solution is to generate all divisions of a given number and check if a division is divisible.
We can solve this problem by storing remainders of each prefix and suffix of the given string and if at any index, prefix reminder and suffix reminder both are zero, then we know that we can break the string at this index. The procedure is explained for the above example,
String = “246904096” All prefix reminders with 12345 are, Prefix 2 reminder with 12345, 2 prefix 24 reminder with 12345, 24 prefix 246 reminder with 12345, 246 prefix 2469 reminder with 12345, 2469 prefix 24690 reminder with 12345, 0 prefix 246904 reminder with 12345, 4 prefix 2469040 reminder with 12345, 40 prefix 24690409 reminder with 12345, 409 prefix 246904096 reminder with 12345, 4096 All suffix reminder with 1024 are, Suffix 6 reminder with 1024, 6 Suffix 96 reminder with 1024, 96 Suffix 096 reminder with 1024, 96 Suffix 4096 reminder with 1024, 0 Suffix 04096 reminder with 1024, 0 Suffix 904096 reminder with 1024, 928 Suffix 6904096 reminder with 1024, 288 Suffix 46904096 reminder with 1024, 800 Suffix 246904096 reminder with 1024, 288 Now we can see that at index 5 both reminders are 0, so the string can be broken into 24680 and 4096.
We can get (i)th suffix reminder by (i – 1)th suffix reminder as, (sr[i] = sr[i – 1] * 10 + s[i]) % f, i.e. just multiply previous reminder by 10 and add current digit and then take reminder by f.
For getting (i)th prefix reminder by (i + 1)th prefix reminder, we can do, (pr[i] = pr[i + 1] + s[i] * base) % s, i.e. add next reminder and current digit multiplied with base value which will be 1 for last digit, 10 for second last digit and so on and then we will take reminder by s overall.
Total time complexity of solution will O(N)
C++
// C++ code to break the number string into// two divisible parts by given numbers#include <bits/stdc++.h>using namespace std;// method prints divisible parts if possible, // otherwise prints 'Not possible'void printTwoDivisibleParts(string num, int f, int s){ int N = num.length(); // creating arrays to store reminder int prefixReminder[N + 1]; int suffixReminder[N + 1]; suffixReminder[0] = 0; // looping over all suffix and storing // reminder with f for (int i = 1; i < N; i++) // getting suffix reminder from previous // suffix reminder suffixReminder[i] = (suffixReminder[i - 1] * 10 + (num[i - 1] - '0')) % f; prefixReminder[N] = 0; int base = 1; // looping over all prefix and storing // reminder with s for (int i = N - 1; i >= 0; i--) { // getting prefix reminder from next // prefix reminder prefixReminder[i] = (prefixReminder[i + 1] + (num[i] - '0') * base) % s; // updating base value base = (base * 10) % s; } // now looping over all reminders to check // partition condition for (int i = 0; i < N; i++) { // if both reminders are 0 and digit itself // is not 0, then print result and return if (prefixReminder[i] == 0 && suffixReminder[i] == 0 && num[i] != '0') { cout << num.substr(0, i) << " " << num.substr(i) << endl; return; } } // if we reach here, then string can' be // partitioned under constraints cout << "Not Possible\n";}// Driver code to test above methodsint main(){ string num = "246904096"; int f = 12345; int s = 1024; printTwoDivisibleParts(num, f, s); return 0;} |
Java
// Java program to break the number string// into two divisible parts by given numberspublic class DivisibleParts{ // method prints divisible parts if // possible, otherwise prints 'Not possible' static void printTwoDivisibleParts(String num, int f, int s) { int N = num.length(); // creating arrays to store reminder int[] prefixReminder = new int[N + 1]; int[] suffixReminder = new int[N + 1]; suffixReminder[0] = 0; // looping over all suffix and storing // reminder with f for (int i = 1; i < N; i++) // getting suffix reminder from // previous suffix reminder suffixReminder[i] = (suffixReminder[i - 1] * 10 + (num.charAt(i - 1) - '0')) % f; prefixReminder[N] = 0; int base = 1; // looping over all prefix and storing // reminder with s for (int i = N - 1; i >= 0; i--) { // getting prefix reminder from next // prefix reminder prefixReminder[i] = (prefixReminder[i + 1] + (num.charAt(i ) - '0') * base) % s; // updating base value base = (base * 10) % s; } // now looping over all reminders to // check partition condition for (int i = 0; i < N; i++) { // if both reminders are 0 and digit // itself is not 0, then print result // and return if (prefixReminder[i] == 0 && suffixReminder[i] == 0 && num.charAt(i ) != '0') { System.out.println( num.substring(0, i) +" " + num.substring(i)); return; } } // if we reach here, then string can' be // partitioned under constraints System.out.println("Not Possible"); } /* Driver program */ public static void main(String[] args) { String num = "246904096"; int f = 12345; int s = 1024; printTwoDivisibleParts(num, f, s); }}// This code is contributed by Prerna Saini |
Python3
# Python3 code to break the # number string into two # divisible parts by given# numbers# method prints divisible # parts if possible, otherwise # prints 'Not possible'def printTwoDivisibleParts(num, f, s): N = len(num); # creating arrays # to store reminder prefixReminder = [0]*(N + 1); suffixReminder = [0]*(N + 1); # looping over all # suffix and storing # reminder with f for i in range(1,N): # getting suffix # reminder from previous # suffix reminder suffixReminder[i] = (suffixReminder[i - 1] * 10 + (ord(num[i - 1]) - 48)) % f; base = 1; # looping over all # prefix and storing # reminder with s for i in range(N - 1,-1,-1): # getting prefix # reminder from next # prefix reminder prefixReminder[i] = (prefixReminder[i + 1] + (ord(num[i]) - 48) * base) % s; # updating base value base = (base * 10) % s; # now looping over # all reminders to check # partition condition for i in range(N): # if both reminders are # 0 and digit itself # is not 0, then print # result and return if (prefixReminder[i] == 0 and suffixReminder[i] == 0 and num[i] != '0'): print(num[0:i],num[i:N]); return 0; # if we reach here, then # string can' be partitioned # under constraints print("Not Possible");# Driver code if __name__=='__main__': num = "246904096"; f = 12345; s = 1024; printTwoDivisibleParts(num,f, s);# This code is contributed # by mits |
C#
// C# program to break the // number string into two // divisible parts by given // numbersusing System;class GFG{// method prints divisible // parts if possible, otherwise// prints 'Not possible'static void printTwoDivisibleParts(String num, int f, int s){int N = num.Length;// creating arrays to// store reminderint[] prefixReminder = new int[N + 1];int[] suffixReminder = new int[N + 1];suffixReminder[0] = 0;// looping over all // suffix and storing // reminder with ffor (int i = 1; i < N; i++) // getting suffix reminder from // previous suffix reminder suffixReminder[i] = (suffixReminder[i - 1] * 10 + (num[i - 1] - '0')) % f; prefixReminder[N] = 0;int base1 = 1;// looping over all // prefix and storing // reminder with sfor (int i = N - 1; i >= 0; i--){ // getting prefix reminder // from next prefix reminder prefixReminder[i] = (prefixReminder[i + 1] + (num[i] - '0') * base1) % s; // updating base1 value base1 = (base1 * 10) % s;}// now looping over all // reminders to check // partition conditionfor (int i = 0; i < N; i++){ // if both reminders are // 0 and digit itself is // not 0, then print result // and return if (prefixReminder[i] == 0 && suffixReminder[i] == 0 && num[i] != '0') { Console.WriteLine(num.Substring(0, i) + " " + num.Substring(i)); return; }}// if we reach here, then // string can' be partitioned // under constraints Console.WriteLine("Not Possible");}// Driver Codepublic static void Main() { String num = "246904096"; int f = 12345; int s = 1024; printTwoDivisibleParts(num, f, s);}}// This code is contributed by mits |
PHP
<?php// PHP code to break the // number string into two // divisible parts by given// numbers// method prints divisible // parts if possible, otherwise // prints 'Not possible'function printTwoDivisibleParts($num, $f, $s){ $N = strlen($num); // creating arrays // to store reminder $prefixReminder = array_fill(0, $N + 1, 0); $suffixReminder = array_fill(0, $N + 1, 0); // looping over all // suffix and storing // reminder with f for ($i = 1; $i < $N; $i++) // getting suffix // reminder from previous // suffix reminder $suffixReminder[$i] = ($suffixReminder[$i - 1] * 10 + (ord($num[$i - 1]) - 48)) % $f; $base = 1; // looping over all // prefix and storing // reminder with s for ($i = $N - 1; $i >= 0; $i--) { // getting prefix // reminder from next // prefix reminder $prefixReminder[$i] = ($prefixReminder[$i + 1] + (ord($num[$i]) - 48) * $base) % $s; // updating base value $base = ($base * 10) % $s; } // now looping over // all reminders to check // partition condition for ($i = 0; $i < $N; $i++) { // if both reminders are // 0 and digit itself // is not 0, then print // result and return if ($prefixReminder[$i] == 0 && $suffixReminder[$i] == 0 && $num[$i] != '0') { echo substr($num, 0, $i)." ". substr($num,$i)."\n"; return; } } // if we reach here, then // string can' be partitioned // under constraints echo "Not Possible\n";}// Driver code $num = "246904096";$f = 12345;$s = 1024;printTwoDivisibleParts($num, $f, $s);// This code is contributed // by mits?> |
Javascript
<script>// javascript program to break the // number string into two // divisible parts by given // numbers// method prints divisible // parts if possible, otherwise// prints 'Not possible'function printTwoDivisibleParts( num, f, s){var N = num.length; // creating arrays to// store remindervar prefixReminder = []var suffixReminder = [] suffixReminder[0] = 0; // looping over all // suffix and storing // reminder with ffor (var i = 1; i < N; i++) // getting suffix reminder from // previous suffix reminder suffixReminder[i] = (suffixReminder[i - 1] * 10 + (num[i - 1] - '0')) % f; prefixReminder[N] = 0;var base1 = 1; // looping over all // prefix and storing // reminder with sfor (var i = N - 1; i >= 0; i--){ // getting prefix reminder // from next prefix reminder prefixReminder[i] = (prefixReminder[i + 1] + (num[i] - '0') * base1) % s; // updating base1 value base1 = (base1 * 10) % s;} // now looping over all // reminders to check // partition conditionfor (var i = 0; i < N; i++){ // if both reminders are // 0 and digit itself is // not 0, then print result // and return if (prefixReminder[i] == 0 && suffixReminder[i] == 0 && num[i] != '0') { document.write(num.substring(0, i) + " " + num.substring(i)); return; }} // if we reach here, then // string can' be partitioned // under constraints document.write("Not Possible"); } // Driver Code var num = "246904096"; var f = 12345; var s = 1024; printTwoDivisibleParts(num, f, s);// This code is contributed by bunnyram19. </script> |
Output:
24690 4096
Time Complexity: O(N)
Auxiliary Space: O(N)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
