#276
Gift Cards
MEDIUMDynamic Programmingpython
Problem Description
A payments pipeline for an e-commerce platform must count the number of valid gift card combinations that produce an exact transaction total, supporting denomination-constrained payment flows.
Determine the number of different ordered arrangements of exactly `N` gift cards (denominations: `$10`, `$30`, `$50`) to purchase an item costing `M` dollars with no remaining balance. Each card slot is distinct, so different orderings count as separate arrangements.
**Input:** `N` (number of cards to use exactly) and `M` (item cost in dollars).
**Output:** Integer count of valid ordered arrangements.
**Key Rules:**
- Must use exactly `N` cards total
- Sum of all cards must equal exactly `M`
- Denominations are `$10`, `$30`, `$50` (reusable)
- Card slots are distinct: [$10, $30] and [$30, $10] are different arrangements
- Return 0 if no valid arrangement exists
Topics
dynamic programmingmathcombinatoricsrecursion
Asked at Companies
tiktok
Solve This Problem
Sign up to access the interactive code editor, run test cases, view the editorial, and get AI-powered feedback on your solution.
Start Solving →