Skip to content

Instantly share code, notes, and snippets.

@abhisheksharma14
Last active August 4, 2022 17:02
Show Gist options
  • Save abhisheksharma14/efa16725e3935f48f167038a724ec3c1 to your computer and use it in GitHub Desktop.
Save abhisheksharma14/efa16725e3935f48f167038a724ec3c1 to your computer and use it in GitHub Desktop.
Competitive Programming Practice.
// Adding numbers with reduced cost.
/*
Victor has an array of size n. He loves to play with these n numbers.
Each time he plays with them, he picks up two consicutive numbers and
adds them. On adding both the numbers, it costs him k*(sum of numbers).
Find the minimum cost of adding all the numbers.
*/
import java.util.*;
import javafx.util.Pair;
public class Main {
public static void main(String[] args) {
Integer inputArray[] = new Integer[] {4,5,6,7}; // from user input array of size n
Integer costMultiplier = 3; // from user input cost multiplier i.e. k
ArrayList<Integer> array = new ArrayList<Integer>(Arrays.asList(inputArray));
ArrayList<Integer> reducedCosts = new ArrayList<Integer>();
Integer totalCost = 0;
while(array.size() > 1) {
Pair<Integer, ArrayList> reduced = costReducer(array);
reducedCosts.add(reduced.getKey());
array = reduced.getValue();
}
for (int i=0; i<reducedCosts.size(); i++ ){
totalCost += reducedCosts.get(i)*costMultiplier;
}
System.out.println(totalCost);
}
public static Pair<Integer, ArrayList> costReducer(ArrayList<Integer> inputArray) {
int minIdx = findMinIdx(inputArray);
Integer cost = 0;
int toRemoveIdx = 0;
if(minIdx == 0) {
cost = inputArray.get(minIdx) + inputArray.get(minIdx+1);
toRemoveIdx = minIdx+1;
} else if(minIdx == inputArray.size()-1){
cost = inputArray.get(minIdx) + inputArray.get(minIdx-1);
toRemoveIdx = minIdx-1;
} else {
if(inputArray.get(minIdx-1) < inputArray.get(minIdx+1)){
cost = inputArray.get(minIdx)+inputArray.get(minIdx-1);
toRemoveIdx = minIdx-1;
} else {
cost = inputArray.get(minIdx)+inputArray.get(minIdx+1);
toRemoveIdx = minIdx+1;
}
}
if(minIdx < toRemoveIdx) {
inputArray.set(minIdx, cost);
inputArray.remove(toRemoveIdx);
} else {
inputArray.set(toRemoveIdx, cost);
inputArray.remove(minIdx);
}
return new Pair<Integer, ArrayList>(cost, inputArray);
}
public static Integer findMinIdx(ArrayList<Integer> list) {
Integer min = Integer.MAX_VALUE;
Integer minIdx = list.size() - 1;
for (Integer i = 0; i < list.size(); i++ ) {
if (min > list.get(i)) {
min = list.get(i);
minIdx = i;
}
}
return minIdx;
}
}
@ankeshki
Copy link

4 errors occured. 1.pair not found

@abhisheksharma14
Copy link
Author

4 errors occured. 1.pair not found

Can you share the testcase?

@Alpanavyas
Copy link

javac /tmp/qkGsnAOZQD/Main.java
/tmp/qkGsnAOZQD/Main.java:5: error: package javafx.util does not exist
import javafx.util.Pair;
^
/tmp/qkGsnAOZQD/Main.java:27: error: cannot find symbol
public static Pair<Integer, ArrayList> costReducer(ArrayList inputArray) {
^
symbol: class Pair
location: class Main
/tmp/qkGsnAOZQD/Main.java:16: error: cannot find symbol
Pair<Integer, ArrayList> reduced = costReducer(array);
^
symbol: class Pair
location: class Main
/tmp/qkGsnAOZQD/Main.java:53: error: cannot find symbol
return new Pair<Integer, ArrayList>(cost, inputArray);
^
symbol: class Pair
location: class Main
4 errors

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment