Minimum number of additions required for all elements to be divisible by the same integer

user_9289545 0
Viewed 604

I got this question on an interview recently.

Given an array of integers, what is the minimum sum of integers to be added so that the resulting array is divisible by some integer?

For example

Given an input array [4, 7, 5, 11, 15]:

If you want to make the array divisible by 2, you would add [0, 1, 1, 1, 1] to each element in the array to get a resulting array of [4, 8, 6, 12, 16]. The sum of the adding array is 4.

If you want to make the array divisible by 3, you would add [2, 2, 1, 1, 0] to each element in the array to get a resulting array of [6, 9, 6, 12, 15]. The sum of the adding array is 6.

This can go on to make the array divisible by 4, 5, and so on. In this example, the correct answer is 4 (making the array divisible by 2).

Proposed solution

The maximum answer is n where n is the length of the array since you can just make the array divisible by 2. My solution is to iterate over all primes from 2 to the max of the input array, find the sum of added numbers, and take the minimum of those sums.

Is there a more efficient solution?

math arrays algorithm
1 Answers

The simple way to do this is to iterate over the array arr and perform a modulo operation of the given integer d on each of its elements. The sum of reminders is the answer.

   int findMinSum(int[] arr, int d) {
        var sum = 0;
        for (var e : arr){
            var mod = e % d;
            sum += mod;
        }
        return sum;
    }
user_57836880
Related