Skip to main content
Talentd

Binary String With Substrings Representing 1 To N - Solution & Explanation

MediumString13 min readAsked at: Gartner, Google
Practice this problem

Problem Statement

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.

 

Example 1:

Input: s = "0110", n = 3
Output: true

Example 2:

Input: s = "0110", n = 4
Output: false

 

Constraints:

  • 1 <= s.length <= 1000
  • s[i] is either '0' or '1'.
  • 1 <= n <= 109

Approach Overview

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.

Approach 1: Iterative Binary Check

This approach involves iterating through each number from 1 to n, converting it to its binary form, and checking if this binary string is a substring of s.

The function iterates over numbers from 1 to n, converts each number to a binary string using Python's builtin bin function, and checks if the resulting binary string (excluding the first two characters '0b') is a substring of s. If any number is not found, it returns False. Otherwise, it returns True after checking all numbers.

Code

PythonC++JavaJavaScriptC#C

Python

C++

Java

JavaScript

C#

C

Complexity

Time Complexity: O(n * m), where m is the maximum length of binary representation of numbers in range 1 to n.
Space Complexity: O(1), since we use a constant amount of extra space.

Try this approach in the editor →

Approach 2: Extend Range Check

This approach involves checking only a part of range [1, n] by evaluating the length of s and maximum numbers that could be represented up to given s length.

This Python function limits necessary checks by only testing up to the minimum of n or 2^length of s, ensuring efficiency by narrowing the range based on possible binary length in s.

Code

PythonC++JavaJavaScriptC#C

Python

C++

Java

JavaScript

C#

C

Complexity

Time Complexity: O(min(n, 2^length(s)) * log(n)).
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Brain Teaser

We observe that the length of string s does not exceed 1000, so string s can represent at most 1000 binary integers. Therefore, if n \gt 1000, then s definitely cannot represent the binary representation of all integers in the range [1,.. n].

Additionally, for an integer x, if the binary representation of x is a substring of s, then the binary representation of \lfloor x / 2 \rfloor is also a substring of s. Therefore, we only need to check whether the binary representations of integers in the range [\lfloor n / 2 \rfloor + 1,.. n] are substrings of s.

The time complexity is O(m^2 times log m) and the space complexity is O(log n), where m is the length of string s and n is the positive integer given in the problem.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Binary Check

Time Complexity: O(n * m), where m is the maximum length of binary representation of numbers in range 1 to n.
Space Complexity: O(1), since we use a constant amount of extra space.

Extend Range Check

Time Complexity: O(min(n, 2^length(s)) * log(n)).
Space Complexity: O(1).

Brain Teaser—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Binary CheckO(n * |s|)O(log n)Simple baseline approach when constraints are small or when demonstrating the direct interpretation of the problem.
Extend Range CheckO((n/2) * |s|)O(log n)Preferred solution for interviews and larger inputs since it reduces the number of substring checks using a binary range observation.

Video Solution

1016. Binary String With Substrings Representing 1 To N (Leetcode Medium) • Programming Live with Larry • 915 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Binary String With Substrings Representing 1 To N easy or hard?
Binary String With Substrings Representing 1 To N is rated Medium difficulty. The implementation is straightforward, but recognizing that only numbers greater than n/2 must be checked requires deeper reasoning about binary representations and substring coverage.
Binary String With Substrings Representing 1 To N Python/Java solution
In Python or Java, the common approach converts each integer to binary using built-in utilities such as bin(i)[2:] in Python or Integer.toBinaryString(i) in Java. Each binary string is then searched inside s using contains or find operations. Applying the n/2 optimization keeps the number of checks manageable.
How to solve Binary String With Substrings Representing 1 To N in O(n)?
A strict O(n) solution is difficult with straightforward substring checks because each search may scan the string. Some optimized implementations use hashing or substring indexing to speed up lookups, but most accepted solutions rely on O(n log n) or O(n * |s|) substring checks with the n/2 optimization.
What is the best approach for Binary String With Substrings Representing 1 To N?
The optimized range check approach is the most practical solution. Instead of checking every integer from 1 to n, only numbers from n down to n/2 + 1 are verified. If those larger binary values appear as substrings, the smaller ones are guaranteed to appear as well. This reduces the number of substring searches while keeping the implementation simple.
Is Binary String With Substrings Representing 1 To N asked at Google/Amazon/Meta?
This problem reflects the type of string and binary reasoning questions commonly used in interviews at companies like Google, Amazon, and Meta. It tests substring search, binary representation, and the ability to recognize mathematical constraints that reduce brute-force work.
What data structure is used in Binary String With Substrings Representing 1 To N?
The core structure used is a string for substring search. The algorithm repeatedly generates binary strings and checks whether they exist inside the main string using built-in search functions. Some optimized variants may use sets or hashing to speed up substring checks.
What is the time complexity of Binary String With Substrings Representing 1 To N?
The typical solution runs in O(n * |s|) time because each number is converted to binary and searched inside the string. With the range optimization that checks only numbers greater than n/2, the effective work becomes roughly O((n/2) * |s|). Space complexity is O(log n) due to storing binary representations.

Ready to solve this problem?

Practice Binary String With Substrings Representing 1 To N with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring