I came across a Python 3 practice question by HackerRank.
Here, I am providing my solution to the problem "BitMasking" with the intention to help you learn and understand Python 3 in a better way.
Please make use of my blog posts for learning purposes only and feel free to ask your questions in the comment box below in case of any doubt.
Click Here to check out all other HackerRank solutions.
Recommended Python Courses:
1. Udemy: Top Python Courses
2. Udemy: 2021 Complete Python Bootcamp From Zero to Hero in Python
3. Udemy: Learn Python Programming Masterclass
4. Coursera: Python for Everybody
5. LinkedIn: Become a Python Developer
6. edX: Programming for Everybody (Getting Started with Python)
7. edureka: Python Programming Certification Training
8. Eduonix: Mighty Python Bundle
Python Problem Description:
Anubhav and Charul are 2 friends travelling to a far away place for ICPC, the biggest competitive coding competition. They decide to play a game.
Anubhav gives Charul a bitmask. He tells Charul that bitmasks are very cool. According to him, A bitmask is a string of binary bits (0s and 1s).
For example
- "0111000" is a bitmask. Anubhav is a naughty but brilliant computer scientist. He has given Charul the following task:
- Given a number N, write a bitmask of length N containing all 0s. Now, he gives Q operations. Each operation contains two numbers (l, r) as input.
An operation can be one of the following
- Update operation: Take the XOR of all the bits in the bitmask from index l to r (both inclusive) with 1.
- Query operation: Count the number of set bits in the bitmask between index l to r (both inclusive).
- He asks Charul to find the sum of all the queries.
Note
1. In case there are no queries, output 0.
2. As the answer can be large, output the answer mod 1000000007
3. Consider 0 based indexing
Input Format:
- The first line contains the input N (the no. of bits)
- The second line contains Q (the no. of operations)
- The next Q lines contain three inputs each 'type','l' and 'r'.
- If type is 0, it's an update operation, else a query operation.
Sample Input:
5
4
0 1 3
1 1 2
0 0 4
1 3 4
Sample Output:
Constraints:
- 1 <= N <= 100000
- 1 <= Q <= 100000
- 0 <= l, r < N
import sys
###############Write your solution below##################
def solution(n, type, left, right, q):
# Write your code here
return 1
mask = solution(n, type, left, right, q)
print(mask)
Task Weightage:
Sr No Task Weightage
1. Preparation of Input param for function 20%
2. Algorithm design (Pseudo code, Time Complexity, Memory Complexity ) 50%
3. Completion of function(Coding) 30%
Note: You can choose any language for coding Java, c++, python, go.
Python 3 Solution:
##### FUNCTION DEFINATION #####
def solution(n, q, operations):
bitmask = [0] * n
print("Bitmask = "+str(bitmask))
sum = 0
if q == 0:
sum = 0
else:
## Perform operations
print("\nOperation Started....")
for operation in operations:
type, l, r = operation
if type == 0:
for i in range(l, r+1):
bitmask[i] = bitmask[i] ^ 1
print("Updated Bitmask = "+str(bitmask))
elif type == 1:
set_bit_count = 0
for i in range(l, r+1):
if bitmask[i] == 1:
set_bit_count = set_bit_count + 1
sum = sum + set_bit_count
print("Sum after query = "+str(sum))
sum = sum % 1000000007
return sum
if __name__ == "__main__":
##### PREPARATION OF INPUT #####
n = int(input("Enter No. of bits (n): "))
# n = 5
print("n = "+str(n))
q = int(input("Enter No. of Operations (q): "))
# q = 4
print("q = "+str(q))
# operations = [(0, 1, 3), (1, 1, 2), (0, 0, 4), (1, 3, 4)]
operations=[]
for i in range(q):
operations.append(tuple(map(int, input("Operation "+str(i+1)+" = ").split(" "))))
print("Operations = "+str(operations))
sum = solution(n, q, operations)
print("\nSum of all queries = "+str(sum))
Output:
[Case-0] Output:
# Enter No. of bits (n): 5
# n = 5
# Enter No. of Operations (q): 4
# q = 4
# Operation 1 = 0 1 3
# Operation 2 = 1 1 2
# Operation 3 = 0 0 4
# Operation 4 = 1 3 4
# Operations = [(0, 1, 3), (1, 1, 2), (0, 0, 4), (1, 3, 4)]
# Bitmask = [0, 0, 0, 0, 0]
# Operation Started....
# Updated Bitmask = [0, 1, 1, 1, 0]
# Sum after query = 2
# Updated Bitmask = [1, 0, 0, 0, 1]
# Sum after query = 3
# Sum of all queries = 3
# >
[Case-1] Output:
# Enter No. of bits (n): 5
# n = 5
# Enter No. of Operations (q): 0
# q = 0
# Operations = []
# Bitmask = [0, 0, 0, 0, 0]
# Sum of all queries = 0
# >
--------------------------------------------------------------------------------
Click here to see solutions for all Machine Learning Coursera Assignments. Click here to see more codes for Raspberry Pi 3 and similar Family. Click here to see more codes for NodeMCU ESP8266 and similar Family. Click here to see more codes for Arduino Mega (ATMega 2560) and similar Family. Feel free to ask doubts in the comment section. I will try my best to answer it.
If you find this helpful by any means, like, comment and share the post.
This is the simplest way to encourage me to keep doing such work.
This is a brute force solution and it's not optimal at all! Can you share a link to the original question so we can look at the best solution that isn't O(N*N)
ReplyDelete