Skip to content

Instantly share code, notes, and snippets.

@nghitruongdev
Last active September 3, 2021 12:54
Show Gist options
  • Save nghitruongdev/f016071d68e2a117b21c651dc3950d4c to your computer and use it in GitHub Desktop.
Save nghitruongdev/f016071d68e2a117b21c651dc3950d4c to your computer and use it in GitHub Desktop.
Calculate the sum of the times any individual element will be copied
package dynamicarray;
import java.util.Scanner;
// Assume that for a dynamic array of size 2 and capacity 4 we perform the following sequence of operations:
// add 5
// add 7
// add 9
// insert 3 1
// insert 6 2
// Here, add x means that we append an element to the array, insert x i means that we insert x to the array at the i-th index (assuming zero-based indexing).
// How many times will array elements be copied during these operations? Note that elements are copied when: array capacity increases.
// In this case, all elements from the old array are copied. an element is inserted into the middle of the array.
// In this case, all elements from the right half of the array are copied after the inserted element, starting at the index of the inserted element
// Write down the sum of the times any individual element will be copied assuming that the scaling factor is 2.
public class Demo {
public static String nextLine(String message){
Scanner scanner = new Scanner(System.in);
System.out.println(message);
return scanner.nextLine();
}
public static void main(String[] args) {
int size = 2;
int capacity = 4;
int sum = 0;
while (true) {
String s = nextLine("Action:");
switch (s) {
case "add":
size += 1;
if (size > capacity) {
sum += size - 1;
capacity *= 2;
}
System.out.println("Size: " + size);
System.out.println("Capacity: " + capacity);
System.out.println("Sum: " + sum);
break;
case "insert":
size += 1;
int index = Integer.parseInt(nextLine("Index: "));
if (size > capacity) {
sum += size - 1;
capacity *= 2;
}
sum += size - 1 - index;
System.out.println("Size: " + size);
System.out.println("Capacity: " + capacity);
System.out.println("Sum: " + sum);
break;
default:
return;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment