Alternative solution for PlusOne(Prob 6.2)

#1

Hi,

I was looking at the Java solution for Problem 6.2 from the 1.4.5 edition of the book(Link to solution in reply below) .

This walks over the list fully 2 times when doing 2 reverses.

I came up with this solution which walks over the list only once:

public class PlusOne {
	public List<Integer> plusOne(List<Integer> A) {
		int n = A.size()-1;
		A.set(n, A.get(n) + 1);
		for(int i=n; i>0 && (A.get(i) == 10); i--) {
				 A.set(i - 1, A.get(i - 1) + 1);
				 A.set(i, 0);
		}
		if (A.get(0) == 10) {
			A.set(0, 0);
			A.add(0,1);
		}
		return A;
	}
}

Since List.add() has constant amortized cost according to the documentation, adding an element to the head of the list would be constant time. Hence I walk over the list in reverse and if 0th element is 10, I make it 0 and add 1 to the head of the list.
Is my implementation correct/efficient?

3 Likes
#2

Link to GitHub Java solution: https://github.com/epibook/epibook.github.io/blob/master/solutions/java/src/main/java/com/epi/PlusOne.java

When posting a topic, it didn’t allow me to add links saying new users can only add 2 links while I had only 1 link.

0 Likes
#3

Hey Bharat,

I think both solutions have the same time complexities, O(n), and you are right. The solution we provided will traverse the list at least two times, and in the worst case, three times; yours will traverse the list at least one time, and in the worst case, two times. Therefore, I personally feel it is a better algorithm with neat implementation. Thanks for sharing this to us.

1 Like
#4

i should point out that for arraylist, add(Object o) has O(1) amortized time, but add(Object o, int index) does not. e.g., if you add objects to the start of an arraylist, each subsequent add takes longer (need to move all elements down by one).

the javadoc for arraylist should be clearer, it says “The add operation runs in amortized constant time, that is, adding n elements requires O(n) time.”, but it’s referring to the first add method (which goes to the end).

i do like your solution, takes advantage of the API,

bye,
adnan

0 Likes
#5

@adnanaziz Thank you for the clarification on the running time of add().

0 Likes