Evening Harmony Partition Count

Published at05 Jan 2026

Like10

You are given a list of notes and a volume limit. Your job is to split the list into contiguous segments so that the sum of each segment does not go above the limit, then count how many different valid partitions exist.

The segments must stay in the original order, because this is a partition problem, not a subset problem. Every cut changes what the next segment can contain.

For example, if notes = [2,2,2,2] and limit = 4, each segment can contain one or two notes, and that leads to 5 valid partitions. If notes = [5] and limit = 3, the answer is 0 because even the single note is already too large to fit into any valid segment.

So the task is to count all ways to cut the array into segments whose sums each stay within the limit.

Example Input & Output

Example 1

Input

notes = [5], limit = 3

Output

Explanation

The single note exceeds the volume limit, so no partition is possible.

Example 2

Input

notes = [2,2,2,2], limit = 4

Output

Explanation

Each segment may contain one or two notes, yielding five partitions.

Example 3

Input

notes = [1,2,1], limit = 3

Output

Explanation

Valid segmentations are [1|2|1], [1|2,1], and [1,2|1].

Algorithm Flow

Recommendation Algorithm Flow for Evening Harmony Partition Count

Solution Approach

This is a natural prefix dynamic programming problem. Let dp[i] mean the number of valid ways to partition the first i notes.

To compute dp[i], we try every possible place where the last segment could start. Suppose the last segment is notes[j..i-1]. If its sum is at most the limit, then every valid partition of the prefix ending at j can be extended by this segment.

That gives the transition:

dp[i] += dp[j]

for every j where the segment sum from j to i - 1 is valid.

Using prefix sums makes it easy to check any segment sum quickly. Then we fill dp from left to right, starting with dp[0] = 1 for the empty prefix.

The final answer is dp[n]. This works well because every partition can be understood as a valid earlier partition plus one last legal segment.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int count_partitions(int[] nums, int k) {
        long total = 0;
        for (int x : nums) total += x;
        if (total % k != 0) return 0;
        long target = total / k;
        int[] ways = new int[k];
        ways[0] = 1;
        long current = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            current += nums[i];
            for (int j = k - 1; j > 0; j--) {
                if (current == j * target) {
                    ways[j] += ways[j-1];
                }
            }
        }
        return ways[k-1];
    }
}

javascript

function count_partitions(nums, k) {
    const total = nums.reduce((a, b) => a + b, 0);
    if (total % k !== 0) return 0;
    const target = total / k;
    const ways = new Array(k).fill(0);
    ways[0] = 1;
    let current = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        current += nums[i];
        for (let j = k - 1; j > 0; j--) {
            if (current === j * target) {
                ways[j] += ways[j-1];
            }
        }
    }
    return ways[k-1];
}

php

function count_partitions($nums, $k) {
    $total = array_sum($nums);
    if ($total % $k !== 0) return 0;
    $target = $total / $k;
    $ways = array_fill(0, $k, 0);
    $ways[0] = 1;
    $current = 0;
    for ($i = 0; $i < count($nums) - 1; $i++) {
        $current += $nums[$i];
        for ($j = $k - 1; $j > 0; $j--) {
            if ($current == $j * $target) {
                $ways[$j] += $ways[$j-1];
            }
        }
    }
    return $ways[$k-1];
}

python

def count_partitions(nums, k):
    n = len(nums)
    total = sum(nums)
    if total % k != 0: return 0
    target = total // k
    if target == 0:
        zeros = nums.count(0)
        if zeros < k: return 0
        # Ways to pick k-1 zeros to split among total zeros
        import math
        return math.comb(zeros - 1, k - 1)
    
    count = 0
    ways = [0] * (k + 1)
    ways[0] = 1
    current = 0
    for i in range(n - 1):
        current += nums[i]
        for j in range(k - 1, 0, -1):
            if current == j * target:
                ways[j] += ways[j-1]
    return ways[k-1]

rust

pub fn count_partitions(nums: Vec<i32>, k: i32) -> i32 {
    let total: i64 = nums.iter().map(|&x| x as i64).sum();
    let k = k as usize;
    if total % (k as i64) != 0 { return 0; }
    let target = total / (k as i64);
    let mut ways = vec![0; k];
    ways[0] = 1;
    let mut current = 0i64;
    for i in 0..nums.len().saturating_sub(1) {
        current += nums[i] as i64;
        for j in (1..k).rev() {
            if current == (j as i64) * target {
                ways[j] += ways[j-1];
            }
        }
    }
    ways[k-1]
}

typescript

function count_partitions(nums: number[], k: number): number {
    const total = nums.reduce((a, b) => a + b, 0);
    if (total % k !== 0) return 0;
    const target = total / k;
    const ways = new Array(k).fill(0);
    ways[0] = 1;
    let current = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        current += nums[i];
        for (let j = k - 1; j > 0; j--) {
            if (current === j * target) {
                ways[j] += ways[j-1];
            }
        }
    }
    return ways[k-1];
}

Related Dynamic Programming Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Evening Harmony Partition Count

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Dynamic Programming Challenges

Twilight Lantern Garden

Lantern Vowel Pathways

Celestial Pattern Synthesis

Lantern Crew Rest Planner

Luminous Script Segmentation Count

Glow Market Profit Planner

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.