Binary String With Substrings Representing 1 To N

Medium

Problem

Given a binary string s and a positive integer n, return true if the binary representation of all the integers in the range [1, n] are substrings of s, or false otherwise.

A substring is a contiguous sequence of characters within a string.

Constraints

1 <= s.length <= 1000
s[i] is either '0' or '1'
1 <= n <= 10^9

Examples

Input: s = "0110", n = 3

Output: true

The binary representations are: 1 = '1', 2 = '10', 3 = '11'. All of these are substrings of '0110': '1' appears at index 1, '10' appears at index 2, '11' appears at index 1.

Input: s = "0110", n = 4

Output: false

The binary representation of 4 is '100', which is not a substring of '0110'.

Loading...

Loading Python...