You are given an array of n integers and two integers m and k. 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 m in the resultant array.

Consider n=4,m=2,k=2 and arr[]=[1,2,3,4,5] let's add 1 to arr[0] and 1 to arr[2] then the final array is [2,2,4,4,5] now there are four elements which are multiples of m=2 I am not getting correct output. Here is my code

import java.util.*;
 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：

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 by m`)
• 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 from k and increment max
  • otherwise break out of the loop (because of the sort, no value remaining can be less than k)

public static int maxDivisors(int m, int k, int[] arr) {
    System.out.println(Arrays.toString(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