CODEWITHSUNDEEP
javaarraylist
Alexander Mills
Alexander Mills

Reputation: 100010

Shifting ArrayList elements to the right

Full disclosure this was an interview question that I didn't get right. Here's the question:

    /*
     * If you have an integer that is too large to be stored as a built-in type
     * like an int or double, you can represent it as an array of single digits.
     * Write a function that will increment such a number by 1. For example, the
     * number 1,235 would be represented as [1, 2, 3, 5] in an array. The
     * function should take the array [1, 2, 3, 5] as input and return the array
     * [1, 2, 3, 6].
     */

I have an ArrayList with each element representing the digit in a base-10 number. I want to create a method to increment the number, and then output that incremented number. So I have this:

package start;

import java.util.ArrayList;
import static java.lang.System.out;

public class InputArray {

    private ArrayList<Integer> value;

    public InputArray(ArrayList<Integer> value) {
        this.value = value;
    }


    private ArrayList<Integer> returnBigNum() {

        ArrayList<Integer> input = this.value;
//      input.set(0,0) // this won't work

        for (int i = input.size() - 1; i >= 0; i--) {

            Integer temp = input.get(i);

            temp++;

            if (temp.equals(10)) {
                input.set(i, 0);
            } else {
                input.set(i, temp);
                return input;
            }
        }
        return input;
    }

    public static void main(String[] args) {

        InputArray ia1 = new InputArray(new ArrayList<Integer>(){{
            add(3);add(9);add(9);add(9);add(9);
        }});

        InputArray ia2 = new InputArray(new ArrayList<Integer>(){{
            add(9);add(9);add(9);
        }});

        ArrayList<Integer> result1 = ia1.returnBigNum();
        out.println(result1);

        ArrayList<Integer> result2 = ia2.returnBigNum();
        out.println(result2);
    }

}

The problem I have is with input that is all 9s, like 999, 9999, 999999, etc. With input = 999, I end up with 000.

So, a quick solution would be to add one element in the zeroeth place at the beginning of the method, then you have final element to iterate over. But the question is then, how do I shift all the elements to the right? And if that is too much computational effort, what is better workaround?

To shift things to the right, is this all that is necessary?

http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html void add(int index, E element) Inserts the specified element at the specified position in this list.

isn't that computationally expensive?

Upvotes: 0

Views: 1726

Answers (2)

m0skit0
m0skit0

Reputation: 25873

Store the numbers in reverse order, that is, index 0 is for 10^0, index 1 is for 10^1 and so on. For example 1,235 would be [5, 3, 2, 1].

PS: The interview question is nonsense. BigInteger is what you have to use.

Upvotes: 4

Stack Exchange Broke The Law
Stack Exchange Broke The Law

Reputation: 58868

You can add a 0 to the start of the list simply with:

//      the element to add
//           |
//           V
input.add(0, 0);
//        ^
//        |
// the index to add it at

Here is the documentation for this overload of the add method.

Upvotes: 4

Related Questions