Python | Check if there are K consecutive 1’s in a binary number

Given K and a binary number, check if there exists k consecutive 1’s in the binary number. Examples:

Input: binary number = 101010101111
            k = 4 
Output: yes
Explanation: at the last 4 index there exists 4 consecutive 1’s

Input: binary number = 11100000 k=5 
Output: no
Explanation: There is a maximum of 3 consecutive 1’s in the given binary.

Approach: Create a new string with k 1’s. Using if condition check if there is new in s. In python if new in s: checks if there is any existence if new in s, hence returns true if there is else it returns a false. Below is the Python implementation of the above approach: 

yes

Time Complexity : O(N)
Auxiliary Space : O(1)

Approach : Using find() method

YES

Time complexity: O(n), where n is the length of s. 
Auxiliary space: O(1), as we are only using a constant amount of memory for the string s, the integer k, and the string res.

Another approach to solve this problem is to use a sliding window approach. In this approach, we can check for the presence of k consecutive 1’s by considering a window of size k and sliding it through the entire binary number.

Here is an example of how this approach can be implemented in Python:

Yes

This approach uses a for loop to iterate through each possible starting index of a sequence of k 1’s in the binary string and then checks if all the subsequent characters in the string at those indices are 1’s using the all() function. If any sequence of k 1’s is found, the function returns True, otherwise, it returns False.

The time complexity of the check_consecutive_ones() function is O(n*k), where n is the length of the input string. This is because the function involves iterating through all the characters in the string and checking if there is a consecutive subsequence of k ones.
The Auxiliary Space of the check_consecutive_ones() function is O(k), The all() function returns True if all the elements in an iterable are True, and False otherwise. 

Approach : Using replace() and len() methods

YES

Time Complexity : O(N)
Auxiliary Space : O(N)

Approach : Using operator.contains() method

Check whether k consecutive 1’s are present in given binary string using operator.contains() method

YES

Time Complexity : O(N) where N is the length of s. 

Auxiliary Space : O(1) as we are only using a constant amount of memory for the string s, the integer k, and the string res

Approach: Using  a regular expression

• Imports the re module
• Sets the input binary string and the number of consecutive 1’s to check using tuple unpacking
• Searches for a pattern of k consecutive 1’s in the binary string using a regular expression with the re.search() function
• Sets the result to “YES” if the pattern is found, and “NO” if it is not, using a ternary operator
• Prints the result to the console.

YES

Time Complexity: O(N) where N is the length of s.

Auxiliary Space: O(N) because the regular expression pattern is created based on the input value of k,.