We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Kth Bit in Nth Binary String

Number: 1667

Difficulty: Medium

Paid? No

Companies: Meta, Amazon

Problem Description

Given two positive integers n and k, we build a binary string Sₙ as follows:

  • S₁ = "0"
  • For i > 1, Sᵢ = Sᵢ₋₁ + "1" + reverse(invert(Sᵢ₋₁)) The problem asks for the kth bit in Sₙ. It is guaranteed that k is valid for the given n.

Key Insights

  • The length of Sₙ is 2ⁿ - 1.
  • The kth bit's location can be determined by comparing k with the middle position (which is always "1").
  • If k is in the left half of Sₙ, it is the same as the kth bit in Sₙ₋₁.
  • If k is in the right half, it corresponds to the inverse of a bit in Sₙ₋₁, specifically at position (2ⁿ - k).

Space and Time Complexity

Time Complexity: O(n), where n is the recursion depth. Space Complexity: O(n), due to the recursion stack.

Solution

We solve the problem recursively by leveraging the recursive structure of the binary string.

  1. Define mid as 2^(n-1), which represents the middle (and always "1") position of Sₙ.
  2. If k equals mid, return "1".
  3. If k is less than mid, the kth bit is in the left half; use recursion on Sₙ₋₁.
  4. If k is greater than mid, find the mirrored index in Sₙ₋₁ using (2ⁿ - k) and invert the result.
  5. The recursion stops at the base case n = 1, where S₁ is "0".

Code Solutions

# Function to find kth bit in nth binary string
def findKthBit(n, k):
    # Base case: if n equals 1, S1 is "0"
    if n == 1:
        return "0"
    
    # Calculate the middle position as 2^(n-1)
    mid = 1 << (n - 1)
    
    # If k is exactly at the middle, return "1"
    if k == mid:
        return "1"
    # If k is in the left half, recursively compute kth bit in S_(n-1)
    elif k < mid:
        return findKthBit(n - 1, k)
    # If k is in the right half, find the corresponding bit in S_(n-1) and invert it
    else:
        corresponding_bit = findKthBit(n - 1, (1 << n) - k)
        return "0" if corresponding_bit == "1" else "1"

# Example usage:
# print(findKthBit(3, 1))  # Expected output: "0"
# print(findKthBit(4, 11)) # Expected output: "1"
← Back to All Questions