Divide large numbers represented as strings in Java
The following article explores the intricate division of large numbers represented as strings in mathematics, highlighting the challenges of traditional methods. Large numbers, often used in fields like cryptography, scientific research, and finance, require a unique approach considering computational resources, algorithmic efficiency, and precision.
Example1 :
Input: number = "12345678901234567890" , divisor = 75
Output: 164609052016460905
Explanation: Upon dividing "12345678901234567890" by 75, the remainderless result is "164609052016460905".
Example2 :
Input: number = “1248163264128256512” , divisor = 125
Output: 9985306113026052
Explanation: "1248163264128256512" is divided by 125 to get "9985306113026052" as the sole remainder.
Using an Optimized Iterative Approach
Algorithm
Step 1: Initialize StringBuilder for the division result.
Step 2: Convert the input number into a character array.
Step 3: Initialize the variable for remainder storage.
Step 4: Iterate through each dividend digit.
Step 5: Calculate the partial dividend by adding the previous iteration's remainder to the current digit.
Step 6: Append the result with a partial quotient.
Step 7: Update remainder as modulus of partial dividend and divisor.
Step 8: Remove leading zeros from the result.
Here is an implementation of dividing a larger number represented as a string using an optimized iterative approach :
FileName:LargeNumberDivision.java
import java.io.*;
public class LargeNumberDivision {
public static String divideLargeNumber(String number, int divisor) {
StringBuilder result = new StringBuilder();
char[] dividendArray = number.toCharArray();
int remainder = 0;
for (int i = 0; i < dividendArray.length; i++) {
// Calculate the partial dividend by adding the remainder from the previous iteration
// multiplied by 10 to the current digit of the dividend
int partialDividend = remainder * 10 + Character.getNumericValue(dividendArray[i]);
// Append the result with the partial quotient obtained by dividing the partial dividend by the divisor
result.append(partialDividend / divisor);
// Update the remainder for the next iteration as the modulus of the partial dividend and the divisor
remainder = partialDividend % divisor;
}
// Remove any leading zeros from the result
for (int i = 0; i < result.length(); i++) {
if (result.charAt(i) != '0') {
// Return the result after removing leading zeros
return result.substring(i);
}
}
// Return an empty string if the result is zero
return "";
}
public static void main(String[] args) {
String number = "12345678901234567890";
int divisor = 75;
System.out.println(divideLargeNumber(number, divisor));
}
}
Output:
164609052016460905
Complexity analysis: The above approach has a time complexity of O(n), where n is the input number, and a space complexity of O(n) due to the use of a `StringBuilder` and constant space requirements of other variables.
Using BigInteger Division Approach
Algorithm
Step 1: Convert the input number string to a BigInteger.
Step 2: Create a BigInteger object for the divisor.
Step 3: Perform division using BigInteger's `divideAndRemainder` method.
Step 4: Extract the quotient from the result.
Step 5: Convert the quotient to a string and return it.
Here is an implementation of dividing a larger number represented as a string using a big integer division approach :
FileName:LargeNumberDivision1.java
import java.math.BigInteger; public class LargeNumberDivision1 { public static String divideLargeNumber(String number, int divisor) { // Convert the input number string to a BigInteger BigInteger dividend = new BigInteger(number); // Create a BigInteger object for the divisor BigInteger bigDivisor = BigInteger.valueOf(divisor); // Perform division using BigInteger's divide method BigInteger[] result = dividend.divideAndRemainder(bigDivisor); // Convert the quotient to string and return return result[0].toString(); } public static void main(String[] args) { String number = "12345678901234567890"; int divisor = 75; System.out.println(divideLargeNumber(number, divisor)); } }
Output:
164609052016460905
Complexity analysis: The above approach has a time complexity of O(n) due to BigInteger's `divideAndRemainder` method and a space complexity of O(1) due to the constant extra space required for the dividend and divisor.