getting wrong output while calculating maximum multiples of certain integer

Question

We have array of size n and their are two integers m and k. we can add any positive number to any element of the array such that the total value that we added doesn't exceed k. so my question is how to find maximize the multiples of m in the resultant array. let say we have n=5 , m=2,k=2 and arr[] = {1,2,3,4,5}. lets add 1 to arr[0] and add 1 to arr[2] the final array will be arr[]={2,2,4,4,5} now there are 4 elements which are multiples of m=2.

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++){
                arr[i]=arr[i]+j;
                if(arr[i]%m==0){
                 count++;
                  
                }
            }
            
          
            
        }
        System.out.println(count);
    }
}

Expected Output:- 3

My output:- 5

Answer 1

I would take a completely different approach. Ask yourself, what you you need to add to a number to make it divisible by m? the answer to that it:

(m - number % m) % m

Apply this to every number of the array then sort those number from low to high. Then take away those numbers from k until it's negative then you know the answer. Putting it together you could do it like this:

public static void main(String[] args) {
    int m =4;
    int k =3;
    int count=0;

    int[] arr ={17,8,9,1,4};

    int[] result = Arrays.stream(arr).map(operand -> (m - operand % m) % m).sorted().toArray();

    for (int i : result) {
        if (k - i >= 0) {
            k = k - i;
            count++;
        }
    }

    System.out.println(count);
}

Answer 2

Ok. I guess I understood the logic.

There's a couple of things you need to do in your code.

1. You need to check if the item is already multiple of m. If it is, inner for needs a break.

2. You need to do the same thing after adding j to the item.

    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);
        }
    }