Last active
September 3, 2021 12:54
-
-
Save nghitruongdev/f016071d68e2a117b21c651dc3950d4c to your computer and use it in GitHub Desktop.
Calculate the sum of the times any individual element will be copied
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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