Check Subset sum divisible by k

Problem Overview

We only care about subset sums modulo k, not their full values.

Intuition

We only care about subset sums modulo k, not their full values. If two prefix sums leave the same remainder, their difference is divisible by k, which immediately gives a non-empty subset. That also implies an early shortcut: if the array has at least k elements, the answer is automatically true by the pigeonhole principle.

Algorithm

1If k == 1, return true because every non-empty subset sum is divisible by 1.
2If n >= k, return true by the prefix-sum remainder pigeonhole argument.
3Otherwise maintain dp[r] = some non-empty subset has sum with remainder r modulo k.
4For each value x, let mod = x % k. Start a new subset with remainder mod.
5Also extend every previously reachable remainder r to (r + mod) % k.
6If remainder 0 ever becomes reachable, return true; otherwise false after all elements.

Example Walkthrough

Input: arr = [3, 1, 7, 5], k = 6

1. Remainders are 3, 1, 1, 5 modulo 6.
2. After processing 7, we can make remainder 4 using subset {3,1}.
3. When 5 arrives, extending remainder 1 gives remainder 0: subset {7,5} has sum 12.
4. A remainder of 0 means a non-empty subset sum is divisible by 6.

Output: true

Common Pitfalls

• Do not track full subset sums up to totalSum unless necessary; modulo states are enough and much smaller.
• The empty subset must not count, so dp starts all false and each element first creates its own singleton remainder.
• When updating remainders in-place, iterate carefully; using a temporary layer is the safest mental model.

Check Subset sum divisible by k.java

Java

// Approach: If arr.length >= k, pigeonhole on prefix sums of the first k elements guarantees
// a non-empty contiguous-block subset (hence a subset) with sum divisible by k.
// Otherwise, DP on remainders: dp[r] = some non-empty subset has sum ≡ r (mod k).
// Time: O(n * k) Space: O(k)

class Solution {

    public boolean divisibleByK(int[] arr, int k) {
        int n = arr.length;
        if (k == 1) {
            return true;
        }
        if (n >= k) {
            return true;
        }

        boolean[] dp = new boolean[k];

        for (int x : arr) {
            int mod = x % k;
            boolean[] next = dp.clone();
            next[mod] = true;
            for (int r = 0; r < k; r++) {
                if (dp[r]) {
                    next[(r + mod) % k] = true;
                }
            }
            dp = next;
            if (dp[0]) {
                return true;
            }
        }

        return dp[0];
    }
}

Was this solution helpful?