Efficient way to solve subset sum variation

Question

Given an integer array, find the maximum number of sums of adjacent elements that are divisible by n.

Example 1:

input: long[] array = [1, 2, 3], n = 7

output: 0

Example 2:

input: long[] array = [1, 2, 4], n = 7

output: 1

Example 3:

input: long[] array = [2, 1, 2, 1, 1, 2, 1, 2], n = 4

output: 6

Constraints:

array.length = 50000

array[index] <= 2^31 - 1

n <= 2^31 - 1

Currently, this is my code:

public static int maxSums(long[] array, long n) {

        int count = 0;

        if (array.length == 1 && array[0] == n) {
            return 1;
            
        } else {
            for (int i = 0; i < array.length; i++) {
                long sum = 0;
                for (int j = i; j < array.length; j++) {
                    sum += array[j];
                    if (sum % n == 0) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

which is essentially the window sliding technique. However, this code runs with time complexity O(n^2) which is pretty slow, and results in Apex CPU Time Limit Exceeded towards the higher end of the constraints. Is there a faster way to solve this?

Answer 1

An approach I just thought of is O(n*m), where n is the actual n parameter and m is the array length.

The algorithm remembers for every subsequence up to the current index what reminder the sequence sum has. This information is stored inside the array called currentMod.

When iterating over the input array this currentMod is updated. We simply add to each possible modulo value of iteration i-1 the value of the input array at index i. The updated array includes the number of subsequence sums ending at index i for each possible reminder: 0, 1, 2 up to n-1.

The element first element of tmpMod at index i includes the number of subsequences that end at index i and have a sum divisible by n. Therefore, we add them to our final result.

Here is the algorithm:

public static int maxSums(int[] array, int n) {
    int[] currentMod = new int[n];
    int count = 0;

    for (int i = 0; i < array.length; i++) {
        // Add +1 to 0 remainder as a new sequence can start at every index which has sum 0
        currentMod[0] += 1;
        
        int[] tmpMod = new int[n];

        for (int j = 0; j < currentMod.length; j++) {
            // For every subsequence reminder of i-1 calculate the reminders of adding element i to every subsequence
            tmpMod[(j + array[i]) % n] += currentMod[j];
        }

        // Add number of subsequence sums that divide by n with remainder 0 to result 
        count += tmpMod[0];
        
        currentMod = tmpMod;
    }

    return count;
}

P.S.: This algorithm is not strictly better/worse than yours. It depends on another input value. This means it depends on your inputs what is more efficient. My algorithm is only better for a case with large arrays and low n values.

EDIT: After a lot of thinking and testing I think I found a good solution. It is O(n) in time complexity. It is also O(n) in space complexity as there can be at most n different remainders with n values in the array.

The algorithm keeps track of the current remainder, which is dividable by the input n from the start. For each new subsequence, we add the 1 at the current remainder. In this way, we already define which total sum (mod n) we need that the subsequence is dividable by n.

public static int maxSums(int[] array, int n) {
    Map<Integer, Integer> currentMod = new HashMap<Integer, Integer>();
    int count = 0;
    int currentZero = 0;

    for (int val : array) {
        currentMod.put(currentZero, currentMod.getOrDefault(currentZero, 0) + 1);

        currentZero = (currentZero + val) % n;

        count += currentMod.getOrDefault(currentZero, 0);
    }

    return count;
}

Also, some comparisons to show that it should work out:

len(array)=50000 and n=1000:

• Your method: 11704 ms
• My old one: 188 ms
• My new one: 13 ms

len(array)=50000 and n=1000000:

• Your method: 555 ms
• My old one: stopped after 2 minutes
• My new one: 6 ms