Partition a Number into Two Divisible Parts in Java
Divide a number (as a string) into two non-empty chunks, the first divisible by a and the second by b. The number is represented by a string and two integers, a and b. The result should be "NO" if the string cannot be split into two non-empty elements and "YES" if it can.
Example 1:
Input:
String str = “153” int a = 15 int b= 3
Output:
Yes, the number can be divisible by two parts of a given number
Explanation:
Suppose we split the given number into parts, i.e., a = 15 and b = 3. Hence, the first part 15 is divisible by 'a', and the second part 3 can be divisible by ‘b’.
Example 2:
Input:
String str = “1024” int a = 5 int b= 8
Output:
Yes, the number can be divisible by two parts of a given number
Explanation:
Suppose we split the given number into parts, i.e., a = 10 and b = 24. Hence, the first part, 10, is divisible by 'a', and the second part can be divisible by '8’.
Example 3:
Input:
String str = “1640” int a = 4 int b= 16
Output:
No, the number can be divisible by two parts of a given number
Explanation:
Suppose we split the given number into parts, i.e., a = 16 and b = 40. Hence, the first part 16 is divisible by 'a', but the second part cannot be divisible by 'b'.
Native Approach:
Maintaining the division modulo by 'a' by checking the string from the left to the right and the division modulo by 'b' by checking the string from the right to the left is an efficient preprocessing approach. The formula below can be used to determine the remaining prefix from 0 to i+1 if we know the remainder from 0 to i after dividing it by a.
The formula (lr[i]*10 + str[i] -'0')%a = lr[i+1).
Similarly, scanning from left to right can be used to find modulo by b. Another rl[] is created to store remainders of b in the left-to-right position.
Implementation:
Filename: Partition1.java
import java.io.*;
import java.util.*;
public class Partition1
{
static void Division(String s, int a, int b)
{
int length = s.length();
// Construct an array with size len+1 and initialise it with 0
// When divided by 'a', store the remainders sequentially from left to right
int[] leftright = new int[length + 1];
leftright[0] = ((int)s.charAt(0) - (int)'0')%a;
for (int i = 1; i < length; i++)
{
leftright[i] = ((leftright[i - 1] * 10) % a +
((int)s.charAt(i)-(int)'0')) % a;
}
// Calculate remainders when 'b' is divided by the number from right to left
int[] rightleft = new int[length + 1];
rightleft[length - 1] = ((int)s.charAt(length - 1) - (int)'0') % b;
int pow = 10;
for (int i= length - 2; i >= 0; i--)
{
rightleft[i] = (rightleft[i + 1] + ((int)s.charAt(i) - (int)'0') * pow) % b;
pow = (pow * 10) % b;
}
// Finding a point that can divide a number in two
for (int i = 0; i < length - 1; i++)
{
// If splitting is not possible
if (leftright[i] != 0)
continue;
// We can divide at i if one of the next two conditions are satisfied.
// a) After str.charAt(i), all characters are 0;
// b) The string that results after str.charAt(i) is divisible by b.
// str.charAt(i) is divisible by b, i.e. str.charAt(i+1..n-1) is divisible by b;
if (rightleft[i + 1] == 0)
{
System.out.println("Yes, the number can be divisible by two parts of a given number");
for (int k = 0; k <= i; k++)
System.out.print(s.charAt(k));
System.out.print(", ");
for (int k = i + 1; k < length; k++)
System.out.print(s.charAt(k));
return;
}
}
System.out.println("No, the number can be divisible by two parts of a given number");
}
public static void main (String[] args)
{
String s = "153";
int a= 15;
int b= 3;
Division(s, a, b);
}
}
Output:
Yes, the number can be divisible by two parts of a given number 15, 3
Complexity Analysis:
The time Complexity is O(n), and the space Complexity is given by O(n), where n is the length of the string.
Approach: By using Built-in Functions
Using the built-in library functions to convert strings to integers and integers to strings, this problem can easily be resolved.
Implementation:
Filename: Partition2.java
import java.util.*;
import java.io.*;
public class Partition2
{
public static String findDivision(String s, int a, int b)
{
for (int i = 0; i < s.length() - 1; i++)
{
// Using substring(), which returns a single part of data
// and it specifies the starting and ending index
String first = s.substring(0, i + 1);
String second = s.substring(i + 1);
if (Integer.parseInt(first) % a == 0
&& Integer.parseInt(second) % b == 0)
{
return first + " " + second;
}
}
return "-1";
}
public static void main(String[] args)
{
String s = "664";
int a= 2;
int b= 16;
String res = findDivision(s, a, b);
if (res.equals("-1"))
{
System.out.print("No, the number can be divisible by two parts of a given number");
}
else
{
System.out.print("Yes, the number can be divisible by two parts of a given number
");
System.out.print(res);
}
}
}
Output:
Yes, the number can be divisible by two parts of a given number 6 64
Complexity Analysis:
The Space Complexity is O(1), and the time Complexity is given by O(n), where n is the length of the string.