Binary String With Substrings Representing 1 To N - Video Solutions

Problem Overview: You get a binary string s and an integer n. The task is to verify that every integer from 1 to n, when written in binary, appears as a substring inside s. If even one binary representation is missing, the result is false.

Approach 1: Iterative Binary Check (Time: O(n * |s|), Space: O(log n))

This approach directly follows the problem definition. Iterate through every number from 1 to n, convert the number to its binary representation, and check whether that binary string exists inside s. Most languages provide a substring search operation like find() or contains(), which makes the implementation simple. The key work is repeated substring searches across the string. While straightforward, this approach may become slow when n is large because each number requires generating a binary string and scanning s. The solution relies heavily on efficient string operations.

Approach 2: Extend Range Check (Time: O((n/2) * |s|), Space: O(log n))

This optimization relies on a useful observation about binary representations. If the binary representation of a number x appears in s, then many smaller numbers already appear as substrings inside larger ones. Specifically, every number in the range 1..n/2 will automatically be covered if all numbers in (n/2, n] exist. Instead of checking every integer, iterate only from n down to n/2 + 1. Convert each value to binary and verify its presence in s. This cuts the search space roughly in half while preserving correctness. The solution still depends on substring matching but reduces the number of checks significantly.

Binary conversion and substring scanning are the main operations, which makes this problem primarily about efficient string handling with a small mathematical observation on binary ranges. Understanding how binary prefixes propagate across numbers is the key insight.

Recommended for interviews: The optimized range check is what most interviewers expect. Starting with the brute-force iterative check shows that you understand the requirement clearly. Then introducing the n/2 observation demonstrates problem-solving skill and familiarity with binary properties, which is the differentiator in interviews.