UVa 713: Adding Reversed Numbers is a straight-forward problem that can be solved using an ad-hoc algorithm. We have discussed a similar problem in a previous blog-post. However, this problem imposes following additional constraint—numbers will be at most 200 characters long–which necessitates the use of BigInteger. Following Java code shows such an ad-hoc algorithm that solves this problem by considering the stated constraints.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.PrintWriter; | |
import java.math.BigInteger; | |
import java.util.Scanner; | |
class Main { | |
private final Scanner in; | |
private final PrintWriter out; | |
public Main(){ | |
in = new Scanner(System.in); | |
out = new PrintWriter(System.out, true); | |
} | |
public Main(Scanner in, PrintWriter out){ | |
this.in = in; | |
this.out = out; | |
} | |
private static BigInteger bigIntAfterRemovingTrailingZeros(String num){ | |
int nonZeroIndex=num.length()-1; | |
for (; nonZeroIndex>=0; nonZeroIndex--){ | |
if (num.charAt(nonZeroIndex) != '0'){ | |
break; | |
} | |
} | |
return new BigInteger(num.substring(0, nonZeroIndex+1)); | |
} | |
private static BigInteger[] readLineAsBigInts(String input){ | |
String [] ints = input.trim().split(" "); | |
BigInteger [] rets = new BigInteger[2]; | |
rets[0] = bigIntAfterRemovingTrailingZeros(ints[0]); | |
rets[1] = bigIntAfterRemovingTrailingZeros(ints[1]); | |
return rets; | |
} | |
private static BigInteger reversedBigInt(BigInteger num1){ | |
BigInteger reversedNum = BigInteger.ZERO; | |
final int _REM = 1; | |
final int _QUOTIENT = 0; | |
while (num1.compareTo(BigInteger.ZERO)>0){ | |
BigInteger [] results = num1.divideAndRemainder(BigInteger.TEN); | |
reversedNum = reversedNum.add(results[_REM]); | |
if(num1.compareTo(BigInteger.TEN)>=0) | |
reversedNum =reversedNum.multiply(BigInteger.TEN); | |
num1 = results[_QUOTIENT]; | |
} | |
return reversedNum; | |
} | |
private static BigInteger getAddRevNumbers(BigInteger num1, BigInteger num2){ | |
return reversedBigInt(reversedBigInt(num1).add(reversedBigInt(num2))); | |
} | |
public void run(){ | |
final int T = Integer.parseInt(in.nextLine().trim()); // no of test cases | |
BigInteger [] numbers; | |
for (int testCase = 0 ; testCase< T ; testCase++){ | |
numbers = readLineAsBigInts(in.nextLine());// read input | |
out.println(getAddRevNumbers(numbers[0], numbers[1]));// print result | |
} | |
} | |
public static void main(String[] args) { | |
Main uva713Solver = new Main(); | |
uva713Solver.run(); | |
} | |
} |
Please leave a comment if you have any question. Thanks.