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 every integer in the range [1, n] is a substring of s, and false otherwise.
s = "0110", n = 3truedef query_string(s, n):
for k in range(n, n // 2, -1):
if bin(k)[2:] not in s:
return False
return Truefunction queryString(s, n) {
for (let k = n; k > Math.floor(n / 2); k--) {
if (!s.includes(k.toString(2))) return false;
}
return true;
}class Solution {
public boolean queryString(String s, int n) {
for (int k = n; k > n / 2; k--) {
if (!s.contains(Integer.toBinaryString(k))) return false;
}
return true;
}
}bool queryString(string s, int n) {
auto toBin = [](int k) {
string b;
while (k) { b += char('0' + (k & 1)); k >>= 1; }
reverse(b.begin(), b.end());
return b;
};
for (int k = n; k > n / 2; k--) {
if (s.find(toBin(k)) == string::npos) return false;
}
return true;
}Explanation
We must confirm that every integer from 1 to n, written in binary, appears somewhere inside s. The naive approach checks all n numbers, but a neat observation lets us check only the upper half.
The key idea: the binary form of any number k ≤ n/2 is a prefix of 2k's binary form (since 2k is just k with a 0 appended). And 2k is somewhere in the range we already check. So if all the larger numbers are present, the smaller ones are present too.
That's why the loop only iterates k from n down to just above n // 2. For each such k we build its binary string and ask whether s contains it as a substring; if even one is missing we return false.
Example: s = "0110", n = 3. Only k = 3 (binary "11") and k = 2 (binary "10") need checking. Both "11" and "10" appear in "0110", so the smaller "1" is guaranteed too, and the answer is true.
If every number in that top half is found, we return true.