I'm working on the following task.
Given an array of
nintegers and two integer numbersmandk.You can add any positive integer to any element of the array such that the total value does not exceed
k.The task is to maximize the multiples of
min the resultant array.
Consider the following example.
Input:
n = 5, m = 2, k = 2, arr[] = [1, 2, 3, 4, 5]
Let's add 1 to the element arr[0] and 1 to arr[2] then the final array would be:
[2, 2, 4, 4, 5]
Now there are four (4) elements which are multiples of m (2).
I am not getting correct output.
My code:
public class Main {
public static void main(String[] args) {
int n = 5;
int m = 4;
int k = 3;
int count = 0;
int[] arr = {17, 8, 9, 1, 4};
for (int i = 0; i < n; i ) {
for (int j = 0; j <= k; j ) {
// check initial
if (arr[i] % m == 0) {
break;
}
// add
arr[i] = arr[i] j;
// check again
if (arr[i] % m == 0) {
count ;
break;
}
}
}
System.out.println("Final Array : " Arrays.toString(arr));
System.out.println("Count : " count);
}
}
CodePudding user response：
You must change 2 line in your code :
if(arr[i]%m==0)
{
count ; // add this line
break;
}
// add
arr[i]=arr[i] 1; // change j to 1
// check again
if(arr[i]%m==0)
{
count ;
break;
}
The first is because the number itself is divisible. and The second is because you add a number to it each time.That is wrong. for example chenge your arr to :
int[] arr ={17,8,10,2,4};
your output is :
Final Array : [20, 8, 16, 8, 4]
and That is wrong because 16-10=6 and is bigger than k=3.
CodePudding user response：
This task boils down to a well-known Dynamic programming algorithm called Knapsack problem after a couple of simple manipulations with the given array.
This approach doesn't require sorting and would be especially advantages when k is much smaller n.
We can address the problem in the following steps:
Iterate over the given array and count all the numbers that are already divisible by
m(this number is stored in the variablecountin the code below).While iterating, for every element of the array calculate the difference between
mand remainder from the division of this element bym. Which would be equal tom - currentElement % m. If the difference is smaller or equal tok(it can cave this difference) it should be added to the list (differencesin the code below) and also accumulated in a variable which is meant to store the total difference (totalDiff). All the elements which produce difference that exceedskwould be omitted.If the total difference is less than or equal to
k- we are done, the return value would be equal to the number of elements divisible bymplus the size of the list of differences.Otherwise, we need to apply the logic of the Knapsack problem to the list of differences.
The idea behind the method getBestCount() (which is an implementation Knapsack problem) boils down to generating the "2D" array (a nested array of length equal to the size of the list of differences 1, in which every inner array having the length of k 1) and populating it with maximum values that could be achieved for various states of the Knapsack.
Each element of this array would represent the maximum total number of elements which can be adjusted to make them divisible by m for the various sizes of the Knapsack, i.e. number of items available from the list of differences, and different number of k (in the range from 0 to k inclusive).
The best way to understand how the algorithm works is to draw a table on a piece of paper and fill it with numbers manually (follow the comments in the code, some intermediate variables were introduced only for the purpose of making it easier to grasp, and also see the Wiki article linked above).
For instance, if the given array is [1, 8, 3, 9, 5], k=3 and m=3. We can see 2 elements divisible by m - 3 and 9. Numbers 1, 8, 5 would give the following list of differences [2, 1, 1]. Applying the logic of the Knapsack algorithm, we should get the following table:
[0, 0, 0, 0]
[0, 0, 1, 1]
[0, 1, 2, 3]
[0, 1, 2, 3]
We are interested in the value right most column of the last row, which is 3 plus 2 (number of elements divisible by 3) would give us 5.
Note: that code provided below can dial only with positive numbers. I don't want to shift the focus from the algorithm to such minor details. If OP or reader of the post are interested in making the code capable to work with negative number as well, I'm living the task of adjusting the code for them as an exercise. Hint: only a small change in the countMultiplesOfM() required for that purpose.
That how it might be implemented:
public static int countMultiplesOfM(int[] arr, int k, int m) {
List<Integer> differences = new ArrayList<>();
int count = 0;
long totalDiff = 0; // counter for the early kill - case when `k >= totalDiff`
for (int next : arr) {
if (next % m == 0) count ; // number is already divisible by `m` we can increment the count and from that moment we are no longer interested in it
else if (m - next % m <= k) {
differences.add(m - next % m);
totalDiff = m - next % m;
}
}
if (totalDiff <= k) { // early kill - `k` is large enough to adjust all numbers in the `differences` list
return count differences.size();
}
return count getBestCount(differences, k); // fire the main logic
}
// Knapsack Algorithm implementation
public static int getBestCount(List<Integer> differences, int knapsackSize) {
int[][] tab = new int[differences.size() 1][knapsackSize 1];
for (int numItemAvailable = 1; numItemAvailable < tab.length; numItemAvailable ) {
int next = differences.get(numItemAvailable - 1); // next available item which we're trying to place to knapsack to Maximize the current total
for (int size = 1; size < tab[numItemAvailable].length; size ) {
int prevColMax = tab[numItemAvailable][size - 1]; // maximum result for the current size - 1 in the current row of the table (with the same number of items available)
int prevRowMax = tab[numItemAvailable - 1][size]; // previous maximum result for the current knapsack's size
if (next <= size) { // if it's possible to fit the next item in the knapsack
tab[numItemAvailable][size] = Math.max(prevColMax, tab[numItemAvailable][size - next] 1); // either the max achieved previous with the Current Size (i.e. value in the previous row) or a value from the previous column of the current row (for size - 1) plus 1 (i.e. with a new item)
} else {
tab[numItemAvailable][size] = Math.max(prevRowMax, prevColMax); // either a value in the previous row or a value in the previous column of the current row
}
}
}
return tab[differences.size()][knapsackSize];
}
main()
public static void main(String[] args) {
System.out.println(countMultiplesOfM(new int[]{17, 8, 9, 1, 4}, 3, 4));
System.out.println(countMultiplesOfM(new int[]{1, 2, 3, 4, 5}, 2, 2));
System.out.println(countMultiplesOfM(new int[]{1, 8, 3, 9, 5}, 3, 3));
}
Output:
3 // input array [17, 8, 9, 1, 4], m = 4, k = 3
4 // input array [1, 2, 3, 4, 5], m = 2, k = 2
5 // input array [1, 8, 3, 9, 5], m = 3, k = 3
CodePudding user response：
I believe the problem is that you aren't processing the values in ascending order of the amount by which to adjust.
To solve this I started by using a stream to preprocess the array. This could be done using other methods.
- map the values to the amount to make each one, when added, divisible by
m. - filter out those that equal to
m' (already divisible bym`) - sort in ascending order.
Once that is done. Intialize max to the difference between the original array length and the processed length. This is the number already divisible by m.
As the list is iterated
- check to see if
k > amount needed. If so, subtract fromkandincrement max - otherwise break out of the loop (because of the sort, no value remaining can be less than
k)
- check to see if
public static int maxDivisors(int m, int k, int[] arr) {
int[] need = Arrays.stream(arr).map(v -> m - v % m)
.filter(v -> v != m).sorted().toArray();
int max = arr.length - need.length;
for (int val : need) {
if (k >= val) {
k -= val;
max ;
} else {
break;
}
}
return max;
}
int m = 4;
int k = 3;
int[] arr ={17,8,9,1,4};
int count = maxDivisors(m, k, arr);
System.out.println(count);
prints
3