BudiBadu Logo

Garden Lantern Seating Ways

Dynamic Programming Hard 1 views
Like15

Garden Lantern Seating Ways asks for the number of selections whose brightness total equals a target, with one strict rule: you cannot pick adjacent seats. Each seat can be chosen or skipped, but choosing index i blocks i-1 and i+1. The result is a count of valid non-adjacent subsets that hit the exact target sum.

A robust approach is dynamic programming with position and remaining-sum state, plus whether the previous seat was chosen (or equivalent index jump logic). At each seat you branch: skip it, or take it if constraints allow and remaining target is sufficient. Because branching grows quickly, memoization or bottom-up DP is important. The final count should be returned modulo 1,000,000,007 to keep numbers bounded on larger inputs.

The judge checks normal arrays, repeated values, empty arrays, and exact-target edge cases. For empty input, answer is one only when target is zero, otherwise zero. Make sure your implementation counts ways, not just feasibility, and does not mutate the source list. This is a hard-level mix of subset-sum reasoning and adjacency constraints, requiring careful state definitions to avoid double counting and to preserve correctness across all branching paths.

When implementing memoization, include every variable that affects future choices in the state key, especially index and remaining target. Missing one dimension may appear to work on small tests but will miscount on larger cases where different paths converge at the same index with different constraints.

Examples

Example 1
Input
brightness = [2,1,2], target = 2
Output
2
Explanation

Either seat 1 alone or seat 3 alone satisfies the requirement.

Example 2
Input
brightness = [2,4,3], target = 5
Output
1
Explanation

Only seats 1 and 3 together meet the brightness target without adjacency.

Example 3
Input
brightness = [1,2,3,4], target = 4
Output
2
Explanation

The sets {1,3} and {4} both sum to 4 while avoiding adjacent selections.

Algorithm Flow

Recommendation Algorithm Flow for Garden Lantern Seating Ways - Budibadu
Recommendation Algorithm Flow for Garden Lantern Seating Ways - Budibadu

Best Answers

java
class Solution {
    public int calculate_seating_ways(int n, int k) {
        if (k < 0 || k > (n + 1) / 2) return 0;
        if (k == 0) return 1;
        return (int) nCr(n - k + 1, k);
    }
    private long nCr(int n, int r) {
        if (r > n) return 0;
        if (r == 0 || r == n) return 1;
        if (r > n / 2) r = n - r;
        long res = 1;
        for (int i = 1; i <= r; i++) {
            res = res * (n - i + 1) / i;
        }
        return res;
    }
}