Check Subset Sum Divisible by K (Dynamic Programming)

Sandhiya Priya
1d
115
0
0

Article

Problem Statement

Given an array of positive integers arr[] and an integer k, determine whether there exists at least one non-empty subset whose sum is divisible by k.

Example 1

Input:

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

Output:

true

Explanation

Subset {7, 5} has sum:

7 + 5 = 12
12 % 6 = 0

Hence, the answer is true.

Example 2

Input:

arr = [1, 2, 6]
k = 5

Output:

false

No subset produces a sum divisible by 5.

Why Not Brute Force?

For an array of size n, every element can either be included or excluded.

Therefore, the total number of subsets is:

2^n

For each subset, we calculate the sum and check whether it is divisible by k.

Complexity

Time: O(2^n × n)
Space: O(1)

This approach is impractical for large values of n.

We need something better.

Key Observation

We are not interested in the exact subset sum.

We only care about:

sum % k

For example, when:

k = 6

Sum = 8
8 % 6 = 2

Sum = 20
20 % 6 = 2

Although the sums are different, their remainder is the same.

This means we only need to remember the k possible remainders:

0
1
2
...
k - 1

Instead of storing large sums, we store only their remainder.

Dynamic Programming State

Create an array:

boolean[] dp = new boolean[k];

Meaning

dp[r] = true

There exists a non-empty subset whose sum gives remainder r.

Example

Suppose:

k = 5

Index : 0 1 2 3 4
Value : F T F T F

This means:

Some subset has remainder 1.
Some subset has remainder 3.

Initial State

Initially, no subset exists.

Index : 0 1 2 3 4
Value : F F F F F

Processing Every Number

Suppose the current number is:

num

There are two choices.

Choice 1: Start a New Subset

Take only the current element.

Example:

num = 13
k = 5

13 % 5 = 3

So,

dp[3] = true

because the subset:

{13}

exists.

Choice 2: Extend Existing Subsets

Suppose we already have:

dp[2] = true

Meaning:

Some subset has remainder 2.

Now add the current number.

Suppose:

num = 7

7 % 5 = 2

The new remainder becomes:

(2 + 7) % 5
= 9 % 5
= 4

Therefore:

dp[4] = true

General Formula

newRemainder = (oldRemainder + num) % k

Why Do We Clone the DP Array?

Suppose:

dp =

F T F F F

Current number:

If we directly update the same array,

dp[0] becomes true.

Later in the same iteration, that new value might again be used, meaning we accidentally use the same element multiple times.

To avoid this, we first copy the array:

boolean[] next = dp.clone();

We update next.

After finishing all updates:

dp = next;

Now every element is used exactly once.

Dry Run

Input

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

Initially

Remainder: 0 1 2 3 4 5
DP:        F F F F F F

Process 3

Start a new subset:

3 % 6 = 3

DP becomes:

Remainder: 0 1 2 3 4 5
DP:        F F F T F F

Possible remainders:

{3}

Process 1

Start a new subset:

1 % 6 = 1

Current remainder:

{1}

Extend the previous subset:

3 + 1 = 4

Possible remainders become:

{1, 3, 4}

DP:

Remainder: 0 1 2 3 4 5
DP:        F T F T T F

Process 7

Start a new subset:

7 % 6 = 1

Already exists.

Extend existing subsets:

Possible remainders:

{1, 2, 3, 4, 5}

Process 5

Start:

5 % 6 = 5

Extend:

1 + 5 = 6
6 % 6 = 0

We obtained remainder:

This means a subset sum is divisible by 6.

Answer:

true

Algorithm

For every element:

Clone the current DP array.
Mark the remainder of the current element.
Extend all existing subsets.
Replace the old DP array with the updated one.
If dp[0] == true, return true.

If every element is processed and remainder 0 never appears, return false.

Java Implementation

class Solution {
    public boolean divisibleByK(int[] arr, int k) {

        boolean[] dp = new boolean[k];

        for (int num : arr) {

            boolean[] next = dp.clone();

            // Start a new subset
            next[num % k] = true;

            // Extend existing subsets
            for (int r = 0; r < k; r++) {
                if (dp[r]) {
                    next[(r + num) % k] = true;
                }
            }

            dp = next;

            // Found a subset divisible by k
            if (dp[0]) {
                return true;
            }
        }

        return false;
    }
}

Complexity Analysis

Time Complexity

For every element, we iterate over all k possible remainders.

O(n × k)

Space Complexity

We maintain two arrays of size k.

O(k)

Key Takeaways

We don't need the actual subset sums—only their remainders modulo k.
The DP array dp[r] records whether a non-empty subset with remainder r is achievable.
For each element, we either start a new subset or extend every previously reachable remainder.
Cloning the DP array ensures each element is used at most once, which is essential for subset problems.
This optimization reduces the solution from O(2ⁿ) brute force to O(n × k) time with O(k) space.

Summary

Instead of exploring every possible subset, this dynamic programming approach tracks only the possible remainders obtained after dividing subset sums by k. Since there are only k distinct remainders, the algorithm efficiently builds all reachable states by either starting a new subset or extending existing ones. This reduces the time complexity from exponential O(2ⁿ) to O(n × k) while using only O(k) additional space.