Binary Trace Debounce - Infosys Online Assessment

Problem Preview

"A physical toggle switch emits a binary trace of length `N`, represented as `s[1], s[2], ..., s[N]`. A raw flip occurs at gap `i` (between `s[i]` and `s[i+1]` for $1 \le i < N$) if `s[i] != s[i+1]`. Due to physical bouncing, the switch uses a debounce window of size `g`. We scan the gaps from left to right (from gap 1 to N - 1) maintaining a lock counter, which is initially 0. For each gap: * If the lock counter is greater than 0, the current gap is **muted**. Even if a raw flip occurs at this gap, it is ignored and does not register. The lock counter then decreases by 1. * If the lock counter is equal to 0 and a raw flip occurs, it **registers** (counts towards the total registered flips), and the lock counter is set to `g - 1`. * If the lock counter is equal to 0 and no raw flip occurs, the lock counter remains 0. Find the number of valid binary traces of length `N` that result in **exactly K** registered flips. Since the count can be large, return the answer modulo 998244353. **Input Format** * The first line contains an integer, `N`, denoting the length of the binary trace. * The second line contains an integer, `K`, denoting the exact number of registered flips required. * The third line contains an integer, `g`, denoting the size of the debounce window. **Constraints** * $1 \le N \le 10^5$ * $0 \le K \le N$ * $1 \le g \le N$"