Tap here to switch tabs
Problem
Submissions

Problem: Valid Binary Strings With Cost Limit

Valid Binary Strings With Cost Limit asks for binary strings of a given length with no adjacent ones and a sum of zero-based one positions within the cost limit, returned in lexicographical order.

Statement

Given two integers n and k, return a list of all valid binary strings of length n sorted in lexicographical order.

A binary string is considered valid if it satisfies the following conditions:

  • It does not contain two consecutive ‘1’{‘1’} characters.

  • The total cost of the string is at most k.

The cost of a binary string is defined as the sum of all 00 based indices where the character is ‘1’{‘1’}.

Constraints:

  • 1≤1 \leq n ≤12\leq 12

  • 0≤0 \leq k ≤‘n‘⋅(‘n‘−1)2\leq \frac{ {`n`} \cdot ( {`n`} - 1)}{2}

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Valid Binary Strings With Cost Limit

Valid Binary Strings With Cost Limit asks for binary strings of a given length with no adjacent ones and a sum of zero-based one positions within the cost limit, returned in lexicographical order.

Statement

Given two integers n and k, return a list of all valid binary strings of length n sorted in lexicographical order.

A binary string is considered valid if it satisfies the following conditions:

  • It does not contain two consecutive ‘1’{‘1’} characters.

  • The total cost of the string is at most k.

The cost of a binary string is defined as the sum of all 00 based indices where the character is ‘1’{‘1’}.

Constraints:

  • 1≤1 \leq n ≤12\leq 12

  • 0≤0 \leq k ≤‘n‘⋅(‘n‘−1)2\leq \frac{ {`n`} \cdot ( {`n`} - 1)}{2}