Find the max value of the same length nails after hammered

Question

I'm trying to solve this problem:

Given an array of positive integers, and an integer Y, you are allowed to replace at most Y array-elements with lesser values. Your goal is for the array to end up with as large a subset of identical values as possible. Return the size of this largest subset.

The array is originally sorted in increasing order, but you do not need to preserve that property.

So, for example, if the array is [10,20,20,30,30,30,40,40,40] and Y = 3, the result should be 6, because you can get six 30s by replacing the three 40s with 30s. If the array is [20,20,20,40,50,50,50,50] and Y = 2, the result should be 5, because you can get five 20s by replacing two of the 50s with 20s.

Below is my solution with O(nlogn) time complexity. (is that right?) I wonder if I can further optimize this solution?

Thanks in advance.

public class Nails {

    public static int Solutions(int[] A, int Y) {
        int N = A.length;
        TreeMap < Integer, Integer > nailMap = new TreeMap < Integer, Integer > (Collections.reverseOrder());
        for (int i = 0; i < N; i++) {
            if (!nailMap.containsKey(A[i])) {
                nailMap.put(A[i], 1);
            } else {
                nailMap.put(A[i], nailMap.get(A[i]) + 1);
            }
        }
        List < Integer > nums = nailMap.values().stream().collect(Collectors.toList());

        if (nums.size() == 1) {
            return nums.get(0);
        }

        //else
        int max = nums.get(0);
        int longer = 0;
        for (int j = 0; j < nums.size(); j++) {
            int count = 0;
            if (Y < longer) {
                count = Y + nums.get(j);
            } else {
                count = longer + nums.get(j);
            }
            if (max < count) {
                max = count;
            }
            longer += nums.get(j);
        }
        return max;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String[] input = scanner.nextLine().replaceAll("\\[|\\]", "").split(",");
            System.out.println(Arrays.toString(input));
            int[] A = new int[input.length - 1];
            int Y = Integer.parseInt(input[input.length - 1]);
            for (int i = 0; i < input.length; i++) {
                if (i < input.length - 1) {
                    A[i] = Integer.parseInt(input[i]);
                } else {
                    break;
                }
            }
            int result = Solutions(A, Y);
            System.out.println(result);
        }
    }
}

Answer 1

Since the array is sorted to begin with, a reasonably straightforward O(n) solution is, for each distinct value, to count how many elements have that value (by iteration) and how many elements have a greater value (by subtraction).

public static int doIt(final int[] array, final int y) {
    int best = 0;
    int start = 0;
    while (start < array.length) {
        int end = start;
        while (end < array.length && array[end] == array[start]) {
            ++end;
        }

        // array[start .. (end-1)] is now the subarray consisting of a
        // single value repeated (end-start) times.
        best = Math.max(best, end - start + Math.min(y, array.length - end));

        start = end; // skip to the next distinct value
    }
    assert best >= Math.min(y + 1, array.length); // sanity-check
    return best;
}

Answer 2

A C++ implementation would like the following where A is the sorted pin size array and K is the number of times the pins can be hammered.
{1,1,3,3,4,4,4,5,5}, K=2 should give 5 as the answer
{1,1,3,3,4,4,4,5,5,6,6,6,6,6,6}, K=2 should give 6 as the answer

int maxCount(vector<int>& A, int K) {
    int n = A.size();
    int best = 0;
    int count = 1;

    for (int i = 0; i < n-K-1; i++) {
        if (A[i] == A[i + 1])
            count = count + 1;
        else
            count = 1;
        if (count > best)
            best = count;
    }
    int result = max(best+K, min(K+1, n));
    
    return result;
} 

Answer 3

First, iterate through all the nails and create a hash H that stores the number of nails for each size. For [1,2,2,3,3,3,4,4,4], H should be:

size     count
 1    :    1
 2    :    2
 3    :    3
 4    :    3

Now create an little algorithm to evaluate the maximum sum for each size S, given Y:

BestForSize(S, Y){
    total = H[S]
    while(Y > 0){
        S++
        if(Y >= H[S] and S < biggestNailSize){
            total += H[S]
            Y -= H[S]
        }
        else{
            total += Y
            Y = 0
        }
    }
    return total;
}

Your answer should be max(BestForSize(0, Y), BestForSize(1, Y), ..., BestForSize(maxSizeOfNail, Y)).

The complexity is O(n²). A tip to optimize is to start from the end. For example, after you have the maximum value of nails in the size 4, how can you use your answer to find the maximum number of size 3?

Answer 4

Here is my java implementation: First I build a reversed map of each integer and its occurence for example {1,1,1,1,3,3,4,4,5,5} would give {5=2, 4=2, 3=2, 1=4}, then for each integer I calculate the max occurence that we can get of it regarding the K and the occurences of the highest integers in the array.

public static int ourFunction(final int[] A, final int K) {         
    int length = A.length;
    int a = 0;
    int result = 0;
    int b = 0;
    int previousValue = 0;

    TreeMap < Integer, Integer > ourMap = new TreeMap < Integer, Integer > (Collections.reverseOrder());
    for (int i = 0; i < length; i++) {
        if (!ourMap.containsKey(A[i])) {
            ourMap.put(A[i], 1);
        } else {
            ourMap.put(A[i], ourMap.get(A[i]) + 1);
        }
    }
    
    for (Map.Entry<Integer, Integer> entry : ourMap.entrySet()) {
        if( a == 0) {
            a++;
            result = entry.getValue();
            previousValue = entry.getValue();
        } else {
            if( K < previousValue) 
                b = K;
            else 
                b = previousValue;
            if ( b + entry.getValue() > result )
                result = b + entry.getValue();
            previousValue += entry.getValue();
        }
    }
    return result;
}

Answer 5

Since the array is sorted, we can have an O(n) solution by iterating and checking if current element is equals to previous element and keeping track of the max length.

static int findMax(int []a,int y) {
    int n = a.length,current = 1,max = 0,diff = 0;
    for(int i = 1; i< n; i++) {
        if(a[i] == a[i-1]) {
            current++;
            diff = Math.min(y, n-i-1);
            max = Math.max(max, current+diff);
        }else {
            current = 1;
        }
    }
    return max;
}

Answer 6

given int array is not sorted than you should sort

public static int findMax(int []A,int K) {
    int current = 1,max = 0,diff = 0;
    List<Integer> sorted=Arrays.stream(A).sorted().boxed().collect(Collectors.toList());
    
    for(int i = 1; i< sorted.size(); i++) {
        if(sorted.get(i).equals(sorted.get(i-1))) {
            current++;
            diff = Math.min(K, sorted.size()-i-1);
            max = Math.max(max, current+diff);
        }else {
            current = 1;
        }
    }
    return max;
}

public static void main(String args[]) {
    List<Integer> A = Arrays.asList(3,1,5,3,4,4,3,3,5,5,5,1);
    int[] Al = A.stream().mapToInt(Integer::intValue).toArray();

    int result=findMax(Al, 5);
    System.out.println(result);
}