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.
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.