1545. Find Kth Bit in Nth Binary String
Difficulty: Medium
Topics: String, Recursion, Simulation
Given two positive integers n and k, the binary string Sn is formed as follows:
- S1 = "0"
- Si = Si - 1 "1" reverse(invert(Si - 1)) for i > 1
Where denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).
For example, the first four strings in the above sequence are:
- S1 = "0"
- S2 = "011"
- S3 = "0111001"
- S4 = "011100110110001"
Return the kth bit in Sn. It is guaranteed that k is valid for the given n.
Example 1:
- Input: n = 3, k = 1
- Output: "0"
- Explanation: S3 is "0111001". The 1st bit is "0".
Example 2:
- Input: n = 4, k = 11
- Output: "1"
- Explanation: S4 is "011100110110001". The 11th bit is "1".
Example 3:
- Input: n = 3, k = 2
- Output: "0"
Constraints:
- 1
- 1 n - 1
Hint:
- Since n is small, we can simply simulate the process of constructing S1 to Sn.
Solution:
We need to understand the recursive process used to generate each binary string Sn and use this to determine the k-th bit without constructing the entire string.
Approach:
-
Recursive String Construction:
- S1 = "0".
- For i > 1:
- Si is constructed as: Si = Si-1 "1" reverse(invert(Si-1))
- This means Si consists of three parts:
- Si-1 (the original part)
- "1" (the middle bit)
- reverse(invert(Si-1)) (the transformed part)
-
Key Observations:
- Si has a length of 2i-1.
- The middle bit (position 2i-1 of Si is always "1".
- If k lies in the first half, it falls within Si-1.
- If k is exactly the middle position, the answer is "1".
- If k is in the second half, it corresponds to the reverse-inverted part.
-
Inverting and Reversing:
- To determine the bit in the second half, map k to its corresponding position in the first half using: k' = 2i - k
- The bit at this position in the original half is inverted, so we need to flip the result.
-
Recursive Solution:
- Recursively determine the k-th bit by reducing n and mapping k until n = 1.
Let's implement this solution in PHP: 1545. Find Kth Bit in Nth Binary String
<?php /** * @param Integer $n * @param Integer $k * @return String */ function findKthBit($n, $k) { ... ... ... /** * go to ./solution.php */ } ?>
Explanation:
- Base Case: If n = 1, Si is "0", so the only possible value for any k is "0".
-
Recursive Steps:
- Calculate the middle index mid which is 2n-1.
- If k matches the middle index, return "1".
- If k is less than mid, the k-th bit lies in the first half, so we recursively find the k-th bit in Sn-1.
- If k is greater than mid, we find the corresponding bit in the reverse-inverted second half and flip it.
Complexity Analysis:
- Time Complexity: O(n) because each recursive call reduces n by 1.
- Space Complexity: O(n) for the recursive call stack.
Example Walkthrough:
-
Input: n = 3 , k = 1
- S3 = "0111001"
- k = 1 falls in the first half, so we look for k = 1 in S2.
- In S2 = "011" , k = 1 corresponds to "0".
-
Input: n = 4 , k = 11
- S4 = "011100110110001"
- The middle index for S4 is 8.
- k = 11 falls in the second half.
- Map k = 11 to the corresponding bit in the first half: k' = 24 - 11 = 5.
- Find k = 5 in S3 , which is "0", then flip it to "1".
By leveraging recursion and properties of the string construction, this solution avoids generating the entire string, making it efficient even for larger n.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
- GitHub
The above is the detailed content of Find Kth Bit in Nth Binary String. For more information, please follow other related articles on the PHP Chinese website!

Long URLs, often cluttered with keywords and tracking parameters, can deter visitors. A URL shortening script offers a solution, creating concise links ideal for social media and other platforms. These scripts are valuable for individual websites a

Laravel simplifies handling temporary session data using its intuitive flash methods. This is perfect for displaying brief messages, alerts, or notifications within your application. Data persists only for the subsequent request by default: $request-

This is the second and final part of the series on building a React application with a Laravel back-end. In the first part of the series, we created a RESTful API using Laravel for a basic product-listing application. In this tutorial, we will be dev

Laravel provides concise HTTP response simulation syntax, simplifying HTTP interaction testing. This approach significantly reduces code redundancy while making your test simulation more intuitive. The basic implementation provides a variety of response type shortcuts: use Illuminate\Support\Facades\Http; Http::fake([ 'google.com' => 'Hello World', 'github.com' => ['foo' => 'bar'], 'forge.laravel.com' =>

The PHP Client URL (cURL) extension is a powerful tool for developers, enabling seamless interaction with remote servers and REST APIs. By leveraging libcurl, a well-respected multi-protocol file transfer library, PHP cURL facilitates efficient execution of various network protocols, including HTTP, HTTPS, and FTP. This extension offers granular control over HTTP requests, supports multiple concurrent operations, and provides built-in security features.

Do you want to provide real-time, instant solutions to your customers' most pressing problems? Live chat lets you have real-time conversations with customers and resolve their problems instantly. It allows you to provide faster service to your custom

The 2025 PHP Landscape Survey investigates current PHP development trends. It explores framework usage, deployment methods, and challenges, aiming to provide insights for developers and businesses. The survey anticipates growth in modern PHP versio

In this article, we're going to explore the notification system in the Laravel web framework. The notification system in Laravel allows you to send notifications to users over different channels. Today, we'll discuss how you can send notifications ov


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

DVWA
Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

SublimeText3 Mac version
God-level code editing software (SublimeText3)

PhpStorm Mac version
The latest (2018.2.1) professional PHP integrated development tool

Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

Zend Studio 13.0.1
Powerful PHP integrated development environment
