SPOJ - ADDREV (Adding Reversed Numbers)

Question

https://www.spoj.com/problems/ADDREV/

My answer to ADDREV challenge on SPOJ (link to the problem given above), written in JAVA, was accepted. However, the timing was 1.23 and memory used was 82M, which doesn't seem impressive/up-to-the-mark.

I'm new to competitive programming and want to know -
a. In what ways can I optimize my code to take up lesser memory and be quicker?
b. Are their any incorrect programming practices that I have unknowingly followed?
c. Which better way is available to solve this problem in Java?

My code:-

import java.util.*;
import java.lang.*;
import java.math.BigInteger; 
class Main
{
 public static void main (String[] args) throws java.lang.Exception
 {
 Scanner obj = new Scanner(System.in);
 int t = obj.nextInt(); obj.nextLine(); //clears the buffer
 for(int i=1;i<=t;++i)
 {
 Scanner obj1 = new Scanner(obj.nextLine());
 StringBuffer b1 = new StringBuffer(obj1.next());
 StringBuffer b2 = new StringBuffer(obj1.next());
 b1.reverse(); b2.reverse();
 BigInteger i1 = new BigInteger(b1+"");
 BigInteger i2 = new BigInteger(b2+"");
 i1 = i1.add(i2);
 b1 = new StringBuffer(i1.toString());
 b1.reverse();
 String a = new String(b1.toString());
 for(int j=0;;j++) //To remove leading zeroes (if any)
 {
 if(a.charAt(j)!='0')
 {
 System.out.println(a.substring(j));
 break;
 }
 }
 }
 }
}

Answer 1

Welcome to Code Review, the first thing I noticed in your code is this:

public static void main (String[] args) throws java.lang.Exception {
 Scanner obj = new Scanner(System.in);
 //later in your code in a for cycle
 Scanner obj1 = new Scanner(obj.nextLine());
}

You don't need to declare main method throws Exception and you have to avoid the resource leak created by not closing the scanner obj and creation of a new scanner for every iteration of the loop. You can rewrite your code in this way using try with resources:

public static void main (String[] args) {
 try (Scanner sc = new Scanner(System.in)) {
 int t = sc.nextInt();
 for(int i = 0;i < t;++i) {
 //here the core code
 }
 }
}

You are using StringBuffer reverse to reverse a BigInteger converted to a String; to reverse an int or a BigInteger you can rely on mod and division by 10 knowing that division by 10 always returns the last digit of the number:

val = 24 //I want to reverse it to number 42
variables val = 24 reverse = 0;
remainder = 24 % 10 , reverse = reverse * 10 + remainder equal to 0 * 10 + 4 = 4,
val = val / 10 equal to 2
remainder = 2 % 10 , reverse = reverse * 10 + remainder equal to 4 * 10 + 2 = 42,
val = val / 10 equal to 0

This can be converted in code with the method reverseBigInteger(BigInteger val):

private static BigInteger reverseBigInteger(BigInteger val) {
 BigInteger reverse = BigInteger.ZERO;
 while (val.compareTo(BigInteger.ZERO) == 1) {
 BigInteger remainder = val.mod(BigInteger.TEN);
 reverse = reverse.multiply(BigInteger.TEN);
 reverse = reverse.add(remainder);
 val = val.divide(BigInteger.TEN);
 }
 return reverse;
}

Then you can rewrite the code of your class in the following way:

public class Main {
 public static void main (String[] args) {
 try (Scanner sc = new Scanner(System.in)) {
 int t = sc.nextInt();
 for(int i = 0; i < t; ++i) {
 BigInteger i1 = sc.nextBigInteger();
 BigInteger i2 = sc.nextBigInteger();
 BigInteger reverse1 = reverseBigInteger(i1);
 BigInteger reverse2 = reverseBigInteger(i2);
 BigInteger sum = reverse1.add(reverse2);
 BigInteger reverseSum = reverseBigInteger(sum);
 System.out.println(reverseSum);
 }
 }
 }
 private static BigInteger reverseBigInteger(BigInteger val) {
 BigInteger reverse = BigInteger.ZERO;
 while (val.compareTo(BigInteger.ZERO) == 1) {
 BigInteger remainder = val.mod(BigInteger.TEN);
 reverse = reverse.multiply(BigInteger.TEN);
 reverse = reverse.add(remainder);
 val = val.divide(BigInteger.TEN);
 }
 return reverse;
 }
}

• NEBI4: This helped reduce time to 0.68 and memory to 75M. However, could you explain what is meant by 'you have to avoid the resource leak created by not closing the scanner obj'?
• dariosicily: @NEBI4 From try with resources : a resource is an object that must be closed after the program is finished with it. When you create a scanner object you have to close it otherwise the memory associated with it will be not released until the termination of the program, so if you are creating more instances of scanner (it should be a lot of them) you could risk to consume all the memory (see for details JVM heap).

Answer 2

I have some suggestion for you.

Use the java.lang.StringBuilder instead of the older java.lang.StringBuffer

The java.lang.StringBuilder is generally faster than the older java.lang.StringBuffer.

Use the same instance of java.util.Scanner

Move the java.util.Scanner of the loop, you can reuse it. you can use the obj instance and use only this instance.

Reuse the same java.lang.StringBuilder instead of creating a new one each time.

You can reuse the same builder by clearing it with the method java.lang.AbstractStringBuilder#setLength and passing zero to the method; this will prevent the object creation to be put on the stack and use less memory than creating lots of instances of the builder.

Extract similar code to methods.

In your code, you can extract some of the code to methods; this will make the code shorter and easier to read. I suggest that you create a method to read the input and revert it as a String.