How can I remove all instances of minimum values from array?

I'm trying to prepare for USACO Bronze by doing some practice problems on Codeforces, and I've been struggling on this one for a good two weeks.

Here's the prompt.

At first, I was iterating through the array, removing the minimum element, storing the length in a variable, and repeating until there weren't any values left.

However, that was very inefficient and was not working well, so I decided to instead count the number of instances of each element, subtract those from.

The value I expected was 8. However, the value I received was one, leading me to think the variable value keeps getting reset and it only print out the number of times the last/greatest instance occurs.

How do I modify my code so that I'm able to successfully remove the number of instances of the minimum element from the array length, store the new length in a variable and repeat this without any of my values getting reset in the process?

Please excuse me if this is a really dumb question since I'm just starting USACO, and I'm not used to competitive programming yet.

public class sort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // System.out.println("PLEASE INSERT AN ELEMENT");
        int x = sc.nextInt();
        int memory[];
        memory = new int[x];
        for (int i = 0; i < x; i++) {
            memory[i] = sc.nextInt();
        }

        Arrays.sort(memory);
        int k = memory.length;
        int mem2[] = new int[x];
        int min = memory[0];
        int array[];
        for (int i = 0; i < k; i++) {
            countFreq(memory, k);
            array = removeElements(memory, min);
            k = k + array.length;
            System.out.println(k);
        }
        System.out.println(k);
        sc.close();
    }

    public static void countFreq(int arr[], int n) {
        boolean visited[] = new boolean[n];

        Arrays.fill(visited, false);
        for (int i = 0; i < n; i++) {
            if (visited[i] == true)
                continue;
            int count = 1;
            for (int j = i + 1; j < n; j++) {
                if (arr[i] == arr[j]) {
                    visited[j] = true;
                    count++;
                }
            }
        }
    }

    public static int[] removeElements(int[] arr, int key) {
        int index = 0;
        for (int i = 0; i < arr.length; i++)
            if (arr[i] != key)
                arr[index++] = arr[i];
        return Arrays.copyOf(arr, index);
    }

    public static int[] addX(int n, int arr[], int x) {
        int j;
        int newarr[] = new int[n + 1];
        for (j = 0; j < n; j++)
            newarr[j] = arr[j];

        newarr[n] = x;

        return newarr;
    }
}

The approach used in the code does not follow the problem description correctly, and the logic for sorting and counting the operations is not correct.

Some problems are:

• The countFreq() method is not used correctly. It's meant to count the frequency of elements in an array, but it's not utilized in the sorting process.
• The removeElements() method is used to remove occurrences of the minimum element from the memory array, but this approach does not simulate the described teleportation process correctly.
• The implemented loop does not match the question.
• You can use Java Collections instead of primitive arrays.

I was based on the prompt you passed, and I did it this way:

Main - Just inputs

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] redPandas = new int[n];
    for (int i = 0; i < n; i++) {
        redPandas[i] = scanner.nextInt();
    }
    scanner.close();

    int seconds = sortingOperationSeconds(redPandas);
    System.out.println(seconds);
}

sortingOperationSeconds - Implementation itself

public static int sortingOperationSeconds(int[] redPandas) {
    Queue<Integer> firstLine = new PriorityQueue<>();
    Queue<Integer> secondLine = new LinkedList<>();

    for (int panda : redPandas) {
        firstLine.offer(panda);
    }

    int seconds = 0;
    while (!firstLine.isEmpty()) {
        int flSize = firstLine.size();
        int flSmallestId = firstLine.peek();
        seconds += flSize;
        for (int i = 0; i < flSize; i++) {
            int currentPanda = firstLine.poll();
            if (currentPanda == flSmallestId) {
                secondLine.offer(currentPanda);
            } else {
                firstLine.offer(currentPanda);
            }
        }
    }

    return seconds;
}

Let’s step by step:

1. Red Panda Queues:

   Queue<Integer> firstLine = new PriorityQueue<>();
   Queue<Integer> secondLine = new LinkedList<>();
   

   Two Queues are created to represent the two lines of red pandas, the firstLine is a PriorityQueue, where the smallest ID always stays at the front of the queue and the secondLine is a LinkedList, where red pandas are moved after being removed from firstLine.

2. Adding Red Pandas to firstLine:

   for (int panda : redPandas) {
       firstLine.offer(panda);
   }
   

   Offers all red pandas from the redPandas array to the firstLine queue.

3. Sorting Operation:

   int seconds = 0;
   while (!firstLine.isEmpty()) {
       int flSize = firstLine.size();
       int flSmallestId = firstLine.peek();
       seconds += flSize;
       for (int i = 0; i < flSize; i++) {
           int currentPanda = firstLine.poll();
           if (currentPanda == flSmallestId) {
               secondLine.offer(currentPanda);
           } else {
               firstLine.offer(currentPanda);
           }
       }
   }
   

   While firstLine is not empty, the loop runs. It calculates the number of red pandas in firstLine (flSize) and the smallest ID in firstLine (flSmallestId). Then, it adds flSize seconds to the seconds counter.

   The inner loop removes red pandas from firstLine one by one. If the ID of the current red panda is equal to the smallest ID (flSmallestId), that red panda is moved to secondLine. Otherwise, it is returned to firstLine.

   This process continues until all red pandas have been moved to secondLine.

The main problem with your current approach is that you are modifying the original array memory while trying to count the occurrences and remove elements. This leads to unexpected behavior and incorrect results.

Instead of modifying the original array, you can use a separate data structure to keep track of the occurrences of each element and remove the minimum element without altering the array.

import java.util.Scanner;
import java.util.Arrays;
public class Sort {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int memory[] = new int[x];
for (int i = 0; i < x; i++) {
memory[i] = sc.nextInt();
}
int min = Arrays.stream(memory).min().getAsInt();
int minCount = (int) Arrays.stream(memory).filter(num -> num == min).count();
int k = x - minCount;
while (minCount > 0) {
memory = removeElements(memory, min);
minCount = (int) Arrays.stream(memory).filter(num -> num == min).count();
k -= minCount;
}
System.out.println(k);
sc.close();
}
public static int[] removeElements(int[] arr, int key) {
return Arrays.stream(arr).filter(num -> num != key).toArray();
}
}

Here's what we did:

1.Instead of using an additional array mem2, we directly use the original array memory.

2.We find the minimum element in the array and count its occurrences.

3.We remove the minimum element from the array in a loop until there are no more occurrences of the minimum element. In each iteration, we update the count of k and recalculate the count of the minimum element to be removed.

By doing this, you can avoid modifying the original array and calculate the correct value of k without resetting any values.