Binary String With Substrings Representing 1 To N

Binary String With Substrings Representing 1 To N - 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.

Input & Output

Example 1 — All Found

$ Input: s = "0110", n = 3

› Output: true

💡 Note: Binary representations: 1="1", 2="10", 3="11". All are substrings of "0110": "1" at index 1, "10" at index 1, "11" at index 2.

Example 2 — Missing Number

$ Input: s = "0110", n = 4

› Output: false

💡 Note: Binary of 4 is "100". The string "0110" does not contain "100" as a substring, so return false.

Example 3 — Single Digit

$ Input: s = "1", n = 1

› Output: true

💡 Note: Only need to check if binary of 1 ("1") exists in "1", which it does.

Constraints

1 ≤ s.length ≤ 1000
s[i] is either '0' or '1'
1 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string s and integer n

Process

Check each number's binary form exists in s

Output

Return true if all found, false otherwise

Key Takeaway

🎯 Key Insight: Convert each number to binary and check substring existence - larger numbers are more restrictive

Asked in

G Google 35 f Facebook 28

The key insight is to check if binary representations of all numbers 1 to n exist as substrings. The optimized approach checks from larger numbers first for potential early termination. Time: O(n × m), Space: O(log n).

Common Approaches

Approach	Time	Space	Notes
✓ Reverse Order Search	O(n × m)	O(log n)	Check larger numbers first as they are more likely to be missing
Brute Force Search	O(n × m)	O(log n)	Convert each number to binary and check if it exists as substring

Reverse Order Search — Algorithm Steps

Start from number n and go down to 1
Convert each number to binary
Return false immediately if any binary representation is missing

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from n

Begin with largest number and work backwards

Early Exit

Stop immediately when a binary is not found

Result

Return result as soon as possible

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void toBinary(int num, char* binary) {
    int index = 0;
    if (num == 0) {
        binary[0] = '0';
        binary[1] = '\0';
        return;
    }
    
    char temp[32];
    int tempIndex = 0;
    while (num > 0) {
        temp[tempIndex++] = (num % 2) + '0';
        num /= 2;
    }
    
    for (int i = tempIndex - 1; i >= 0; i--) {
        binary[index++] = temp[i];
    }
    binary[index] = '\0';
}

int solution(char* s, int n) {
    for (int i = n; i >= 1; i--) {
        char binaryRep[32];
        toBinary(i, binaryRep);
        if (strstr(s, binaryRep) == NULL) {
            return 0;
        }
    }
    return 1;
}

int main() {
    char s[1000];
    int n;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &n);
    int result = solution(s, n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

Still need to check all numbers in worst case, each taking O(m) time

✓ Linear Growth

Space Complexity

O(log n)

Space for binary representation of largest number

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Reverse Order Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler