Count Ordered Sequences That Sum to a Target
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Count Ordered Sequences That Sum to a Target
Given a positive target n and a set of unique positive order sizes, count the distinct ordered sequences of any length whose elements sum exactly to n. The same order size may be used repeatedly. Two sequences with the same elements in a different order are distinct.
## Function Contract
Implement `count_order_sequences(n, sizes) -> int`.
## Constraints
- 1 <= n <= 10000.
- 1 <= number of sizes <= 100.
- Every size is unique and between 1 and n.
- The answer is guaranteed to be at most 2^53 - 1.
## Examples
```text
n = 3, sizes = [1, 2]
output = 3
```
```text
n = 3, sizes = [2]
output = 0
```
```hint Distinguish order explicitly
For sizes `[1, 2]`, confirm that `[1, 2]` and `[2, 1]` are counted separately.
```
```hint Check unreachable totals
Include a target that cannot be formed because all allowed sizes share an incompatible common divisor.
```
Overview: Given a positive target n and a set of unique positive order sizes, count the distinct ordered sequences of any length whose elements sum exactly to n. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given a positive target `n` and unique positive allowed sizes, count all finite ordered sequences whose elements sum exactly to `n`. A size may be reused, and two sequences with the same elements in a different order are distinct.
Constraints
- 1 <= n <= 10000; 1 <= len(sizes) <= 100.
- Every size is unique and lies from 1 through n; sizes may be reused in a sequence.
- Sequence order matters and the exact answer is at most 2^53 - 1.
Examples
Input: (1, [1])
Expected Output: 1
Explanation: The only sequence is one occurrence of size one.
Input: (3, [1, 2])
Expected Output: 3
Explanation: The valid ordered sequences are 1+1+1, 1+2, and 2+1.
Hints
- For sizes 1 and 2, compare the two different orders that reach target 3.
- Test one size equal to the target and a target unreachable from all allowed sizes.
- Include the maximum target with many large allowed sizes and a wide but exact result case.
Community answers
Answer by el_bald
#include
using namespace std;
typedef long long ll;
class Solution {
public:
long long count_order_sequences(int n, const std::vector& sizes) {
vector dp(n + 1); dp[0] = 1;
int m = sizes.size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if (i + sizes[j] <= n) {
dp[i + sizes[j]] += dp[i];
}
}
}
return dp[n];
}
};