ArrayList Capacity Growth
Problem
A dynamic array starts empty with capacity 0. The first add makes the capacity 10. When the array is full and you add one more element, the new capacity is the old capacity plus half of it (rounded down), like Java's ArrayList. Read n, the number of adds. Print the final capacity and the number of times the array grew (the first allocation counts as one).
Constraints
- 0 <= n <= 10^6
Examples
Input
11
Output
capacity: 15 resizes: 2
Solutions
Growing by a factor (here 1.5) makes adding an element cost O(1) on average (amortized), even though one resize copies all elements. Growing by a fixed number would make n adds cost O(n^2). Real ArrayList does the same, so a known size in the constructor avoids the copies.
/*
* Problem : Simulate growth.
* Input : One integer n.
* Output : Two lines.
* Approach: Simulation.
* Time : O(n)
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String[] solve(long n) {
// Step 1: capacity = the size of the internal array. size = how many elements are stored.
long capacity = 0;
int resizes = 0;
for (long size = 0; size < n; size++) {
// Step 2: When the array is full, make a bigger one. The first array has capacity 10. Later ones grow by 50 percent.
if (size == capacity) {
capacity = capacity == 0 ? 10 : capacity + (capacity >> 1);
resizes++;
}
}
return new String[] {"capacity: " + capacity, "resizes: " + resizes};
}
public static void main(String[] args) {
long n = new Scanner(System.in).nextLong();
System.out.println(String.join("\n", solve(n)));
}
}
Hints (1)
- Why does growing by a factor give O(1) amortized adds?