Posted by JH

## Add / Multiply To Collection

Create a class of integer collection that supports ‘add to all’ that adds a given number to all the elements in the collection at this point
3 APIs:
append(int x),
get(int idx),
in O(1) time.

Follow-up
Implement another API
multipy_to_all(int x)
in O(1) time.

## Solution

A collection that supports append(x) and get(i) can be a vector or an array list.
To enable add to all in O(1), have an integer value ‘addition’ that records the values added to the collection.
For example, if the collection is currently A = [1, 2, 3], int addition = 0

call get(idx = 2)
returns A + addition = 9

call append(4)
update collection to [1, 2, 3, -2]
where -2 comes from (4 - addition) because the newly appended number was not involved with the previous add_to_all calls.

# Solution to Follow-up

Can we apply the same approach as above to multiply_to_all() by having an integer to keep track of the current factor?
See an example,
A = [1, 2, 3], factor = 3

call append(4)
then we will append 4/3 = 1.3333.. into the collection, which is kind of lousy.

To avoid the hassle on dealing with decimal numbers, we create another vector to keep track of the current factor when a number is appended.

e.g.
A = , factor = 1
F = 

call append(5)
A = [1, 5], factor = 1
F = [1, 1]

call multiply_to_all(2)
A = [1, 5], factor = 2
F = [1, 1]

call append(10)
A = [1, 5, 10], factor = 2
F = [1, 1, 2]

call multiply(3) and then append(20)
A = [1, 5, 10, 20], factor = 2 * 3 = 6
F = [1, 1, 2, 6]

call get(idx)
return A[idx] * factor / F[idx]

To enable both add_to_all and multiply_to_all
When a new factor T comes in, not only update the factor variable by factor = factor * T, also update the addition variable by addition = addition * T;
When appending a number X, append (X - addition).
When getting a number at idx, get (A[idx] * factor/F[idx] + addition).

## Implementation

``````public class AddToAllCollection {
List<Integer> collection = new ArrayList<>();
List<Integer> divisors = new ArrayList<>();
int factor = 1;
int set0 = -1;

public void append(int x) {
}

public int get(int index) {
if(index >= collection.size()) throw new RuntimeException();
return collection.get(index) * (factor / divisors.get(index)) + addition;
}

}

public void multiply_to_all(int x) {
if(x == 0) {
factor = 1;
set0 = collection.size() - 1;
} else {
factor *= x;
}
}
}
``````