Given a sorted array like [1,2,4,4,4]. Each element in the array should occur exactly same number of times as element. For Example 1 should occur 1 time, 2 should occur 2 times, n should occur n times, After minimum number of moves, the array will be rendered as [1,4,4,4,4]

Original                          Shifted                   Min Moves       Reason
[1,2,4,4,4]                       [1,4,4,4,4]               2               delete 2 and insert 4
[1, 1, 3, 4, 4, 4]                [1,4,4,4,4]               3               delete 1,3 an insert 4
[10, 10, 10]                      []                        3               delete all 10s
[1, 1, 1, 1, 3, 3, 4, 4, 4, 4, 4] [1, 3, 3, 3, 4, 4, 4, 4]  5               delete 1,1,1,4 and insert 3

We are allowed to delete/drop some elements totally, as explained above.

I need to find the minimum number of rotations/moves required to get the shifted version. So, I have written below logic to find the min number of moves required on original array.

public static int minMoves(int[] data) {
    Map<Integer, Integer> dataMap = new HashMap<>();
    for(int i=0; i<data.length;i  ) {
        if(dataMap.containsKey(data[i])) {
            dataMap.put(data[i], dataMap.get(data[i]) 1);
        }else {
            dataMap.put(data[i], 1);
        }
    }
    
    System.out.println("Map - " dataMap);
    
    int[] minOperations = {0};      
    dataMap.forEach((digit,frequency)->{            
        if(digit!=frequency) {
            if(digit<frequency) {
                minOperations[0]  = (frequency-digit);
            }else if(digit>frequency && (digit-frequency)<=minOperations[0]) {
                minOperations[0]  = digit-frequency;
            }else {
                minOperations[0]  = frequency;
            }   
        }                               
        System.out.println(digit "  " frequency "  " minOperations[0]);
    });     
    return minOperations[0];
}

The above logic is working fine for above stated cases. But it's failing for few cases.

Failed Case - [1, 2, 2, 2, 5, 5, 5, 8] should return 4, But it's returning 5.

I feel my solution has few problems

1. Not optimistic/Less performant
2. Failing on edge cases
3. Not following any algorithmic approach

Please help to point out. What is the right approaches/algorithms available to solve this in more efficient manner.

More Explanation:

There is an array A of N integers sorted in non-decreasing order. In one move, you can either remove an integer from A or insert an integer before or after any element of A. The goal is to achieve an array in which all values X that are present in the array occur exactly X times.

Given A = [1, 2, 2, 2, 5, 5, 5, 8], your function should retum 4. You can delete the 8 and one occurrence of 2, and insert 5 twice, resulting in [1, 2, 2, 5, 5, 5, 5, 5] after four moves. Notice that after the removals, there is no occurrence of 8 in the array anymore.

given an array A retums the minimum number of moves after which every value X in the array occurs exactly X times. Note that it is permissible to remove some values entirely, if appropriate.

What is the minimum number of moves after which every value X in the array occurs exactly X times?

CodePudding user response：

The error is in this comparison:

(digit-frequency)<=minOperations[0]

There is no logic in comparing with the intermediate, running sum minOperations[0]. It should compare the following two:

• How many insert operations are needed to get to the required number of digits -- this is the left side of the comparison (OK)

• How many delete operations are needed to remove all these digits, this is frequency

So that comparison should be:

digit - frequency <= frequency

Some other remarks:

• As you say the input is sorted, there is no need to create a Map. You can immediately count the number of digits as you iterate from left to right through the array, and at the same time update minOperations.

• There is no need to make minOperations an array. It can be just a primitive.

• The number of expressions to check can be reduced a bit, by using abs and min

Here is how you could update your code:

import java.lang.Math.*;

// ...

public static int minMoves(int[] data) {
    int minOperations = 0;
    for(int i = 0, j = 0; i < data.length; i = j) {
        while (j < data.length && data[i] == data[j]) j  ;
        int frequency = j - i;
        minOperations  = Math.min(Math.abs(data[i] - frequency), frequency);
    }
    return minOperations;
}