How can I remove these nested for-loops in my java code?

Question

I'm in an algorithms class and we're required to make a program that does addition with very long numbers by loading them into linked lists. I see a lot of examples online with using only two linked lists, but mine requires more than just two numbers.

import java.util.*;


public class longNumbersLinkedListCompleted
{

public static void main(String[] args)
{
    Scanner stdIn = new Scanner(System.in);
    String longNumber = "";
    LinkedList mainList = new LinkedList();
    LinkedList sumList = new LinkedList();
    LinkedList temp = null;

    //declare other variables
    int sum = 0;
    int carry= 0;
    int maxWidth = 0;

    System.out.println("Enter a Number");
    longNumber = stdIn.nextLine();
    //repeatedly input longNumbers, using -1 to indicate that you are done
    while(!longNumber.equals("-1")){

        //add a new LinkedList at the beginning of the mainList
        mainList.addFirst(new LinkedList());

        //use get(0) to set temp to be this new LinkedList
        temp = (LinkedList) mainList.get(0);

        //for each character in your longNumber, subtract 48 to get the digit and then add it
        //at the beginning of temp
        for (int i = 0; i < longNumber.length(); i++){
            temp.addFirst((int)(longNumber.charAt(i)-48));        
        }

        //keep track of maxWidth, the number of digits of the widest longNumber input so far
        if(maxWidth < longNumber.length()){
            maxWidth = longNumber.length();
        }

        System.out.println("Enter a Number");
        longNumber = stdIn.nextLine();
    }

    //make maxWidth passes
    //initialize carry to be 0
    //in each pass, loop through all of the LinkedLists in mainList
    //for each one, let temp be the Linked List for one longNumber
    //if temp is not empty, remove its first entry and add to the sum
    for(int i = 0; i < maxWidth; i++){
        sum = 0;

        for(int j = 0; j < mainList.size(); j++){
            temp = (LinkedList)mainList.get(j);
            if(temp.size() > 0){
                sum += (int)temp.removeFirst();
            }
        }
        //add sum%10 at the beginning of sumList
        //set carry equal to sum/10 (integer division)
        sumList.addFirst((sum+carry)%10);
        carry = (sum + carry) / 10;
    }

    //Now ready for output
    //if carry at the end of processing is not 0, print it and stay on the same line
    //repeatedly remove one digit from the beginning of sumList until all have been removed
    //for each, add a 48 to get a character and print it out on the same line
    if(carry != 0){
        System.out.print(carry);
    }
    for(int i = sumList.size(); i > 0; i--){
        System.out.print((char)((int)sumList.removeFirst()+48));
    }

    //remove the digits from sumList until empty

}//end main

}//end class

The comments are from the professor, so it kinda sounded like he wanted a nested for-loop, but in class today he mentioned not using them, and since the whole class is about making code better, it seems counter-intuitive to use something that's O(n^2).

I appreciate any help you folks can give!

Answer 1

The only way I can see to avoid the nested for loops is to do the transposition as you read in the long numbers, i.e. build the sums in the while loop as you are going along.

Something like:

List<Integer> sums = new ArrayList<>();
while(!longNumber.equals("-1")){
  for (int i = 0; i < longNumber.length(); ++i) {
    // Process the digits in reverse.
    int digit = Character.getNumericValue(longNumber.charAt(longNumber.length() - 1 - i));

    if (i >= sums.length()) {
      sums.add(digit);
    } else {
      sums.set(i, sums.get(i) + digit);
    }
  }

  longNumber = stdIn.nextLine();
}

(Note that this is still a nested loop; you simply have to do that to loop until you've read all the numbers, and to read every digit in those numbers).

Then the following inner nested for loop is unnecessary, as the sum has already been calculated:

// This is the equivalent of the for(int i = 0; i < maxWidth; i++){ loop.
for (int sum : sums) {
  sumList.addFirst((sum+carry)%10);
  carry = (sum + carry) / 10;
}

(Of course, you can also fold that second loop into the while loop, and avoid creating sums at all).