Bit Manipulation Questions Part 4
30. (LC 462) Minimum Moves to Equal Array Elements II
Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.
def minMoves2(nums):
nums.sort()
median = nums[len(nums) / 2]
return sum(abs(num - median) for num in nums)
# Less magic
def f(a):
moves = 0
value = int(sum(a) / len(a))
for n in a:
moves += abs(value - n)
return moves
31. (LC 1573) Number of Ways to Split a String
Given a binary string s, you can split s into 3 non-empty strings s1, s2, and s3 where s1 + s2 + s3 = s. Return the number of ways s can be split such that the number of ones is the same in s1, s2, and s3. Since the answer may be too large, return it modulo 10^9 + 7.
Solution
def numWays(s):
mod = 10**9+7
cnt = s.count('1')
if cnt == 0: return (len(s)-1)*(len(s)-2)//2 % mod
if cnt % 3 != 0: return 0
ones = []
for i,x in enumerate(s):
if x == '1': ones.append(i)
return (ones[cnt//3] - ones[cnt//3-1]) * (ones[2*cnt//3]- ones[2*cnt//3-1]) % mod
# possible rewrite for the last part (n_ones - is number of ones in each cut,
# indices - indices where we have 1s)
n_ones = int(ones / 3)
return (indices[n_ones] - indices[n_ones - 1]) + (
indices[2 * n_ones] - indices[2 * n_ones - 1]
Explanations of the basic math.
How to count the number of possible ways to cut a string.
return (ones[cnt//3] - ones[cnt//3-1]) * (ones[2*cnt//3]- ones[2*cnt//3-1]) % modWays to cut a string with only 0s
32. (LC 342) Power of Four
(easy) Given an integer n, return true if it is a power of four. Otherwise, return false. An integer n is a power of four, if there exists an integer x such that n == 4**x.
### Solution 1 (recursion)
def isPowerOfFour(num):
if num <= 0: return False
if num == 1: return True
if num % 4 == 0:
return isPowerOfFour(num / 4)
return False
### Solution 2 (BIT MANIPULATION)
def isPowerOfFour(self, num):
return num > 0 and (num & (num - 1)) == 0 and (num & 0x55555555) != 0
(num & 0x55555555) != 0
>>> bin(0x55555555)
'0b1010101010101010101010101010101'
If we look at examples of numbers that are powers of 4:
>>> 4**2
16
>>> 4**3
64
>>> bin(4)
'0b100'
>>> bin(16)
'0b10000'
>>> bin(64)
'0b1000000'
We see that such numbers always have an even number of zeros, and 1 is at an odd position. Hence when & compared with a mask ..1010101, the 1 in 10000 should align with a 1 in the mask.
(num & (num - 1))
Again, because a num power of 4 is of format a 1 and all zeros like 10000, 10000 & 10000-1 = 0, 10000 & 1111 = 0
33. (LC 762) Prime Number of Set Bits in Binary Representation
(Easy) Given two integers left and right, return the count of numbers in the inclusive range [left, right] having a prime number of set bits in their binary representation.
Recall that the number of set bits an integer has is the number of 1’s present when written in binary. For example, 21 written in binary is 10101, which has 3 set bits.
Also recall that 1 is not a prime, 2 is the smallest prime.
### V3
'''One function for one task.'''
import math
def prime_num_of_bits(l, r):
def count_bits(n):
return n.bit_count()
def is_prime(bits):
if bits == 1 or bits == 0:
return False
if bits == 2:
return True
for i in range(2, int(math.sqrt(bits)) + 1):
if bits % i == 0:
return False
return True
ans = [x for x in range(l, r + 1) if is_prime(count_bits(x))]
return len(ans)
print(prime_num_of_bits(10, 15)) # 5
### Solution 1
'''In this version we count the number of set bits in the main function.
In the helper function we identify if that number is prime.'''
import math
def is_prime(n):
if n==1:
return False
elif n==2:
return True
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
return False
return True
def count_set_bits(n1, n2):
primes = [x for x in range(n1, n2+1) if is_prime(bin(x)[2:].count('1'))]
return len(primes)
print(count_set_bits(6, 10)) #4
print(count_set_bits(10, 15)) #5
### Solution 2
'''In this version the helper function both counts the set bits using bit operators.
The main function only makes a list of valid results, calling the helper function.'''
import math
def f17(x):
'''number of set bits is a prime number'''
count = 0
while x:
x &= (x-1)
count +=1
if count == 1:
return False
for i in range(2, int(math.sqrt(count))+1):
if count % i == 0:
return False
return True
# Verify f17
print(f17(300)) #'0b100101100'
print(f17(21)) #'0b10101'
print(f17(6)) #'0b110'
# OUT
# False
# True
# True
def f18(x,y):
'''For numbers in range x, y: how many nums have prime number of set bits'''
res = [i for i in range(x, y+1) if f17(i)]
print(res)
return len(res)
print(f18(6, 10))
# OUT
# [6, 7, 9, 10]
# 4
34. (LC 645) Set Mismatch
(Easy) You have a set of integers <s>, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in <repetition of one number> and <loss of another> number.
You are given an integer array <nums> representing the data status of this set after the error. Find the number that occurs twice and the number that is missing and return them in the form of an array.
Solutions seem to assume that the given range definitely starts with 1. And the missing number comes right after the duplicate.
# using set, sum
### Solution 1
def findErrorNums(nums):
return [sum(nums) - sum(set(nums)), sum(range(1, len(nums)+1)) - sum(set(nums))]
# OR
def find_dup_mis(a):
dup = sum(a) - sum(set(a))
mis = sum(list(range(1, len(a) + 1))) - sum(set(a))
return [dup, mis]
# Breaking it down
def find_error(a):
sum1 = sum(a)
sum2 = sum(set(a))
dup = sum1 - sum2
sum3 = sum(range(len(a)+1))
missing = sum3 - sum2
return [dup, missing]
a = [1,2,3,4,4,6,7]
print(find_error(a)) #[4, 5]
# using bit manipulation
def find_dup_mis2(a):
# finding mis (make list = our a + full list = [1,1,2,2,>3<,4,4])
mis = 0
L = list(set(a)) + list(range(1, len(a) + 1))
mis = 0
for n in L:
mis ^= n
# finding dup (use num^num=0)
for i in range(len(a)):
if a[i] ^ a[i + 1] == 0:
dup = a[i]
break
return [dup, mis]
a = [1, 2, 2, 4]
print(find_dup_mis2(a)) #[2, 3]
35. (LC 371) Sum of Two Integers
(Medium) Given two integers a and b, return the sum of the two integers without using the operators + and -. Constraints: -1000 <= a, b <= 1000
# Solution 1
class Solution(object):
def getSum(self, a, b):
return sum([a,b])
# Solution 2 rewrite
import math
def summing(m, n):
return math.log(math.e**m * math.e**n)
print(summing(5, 4)) #9.0
# Solution 2
class Souluton:
def getSum(self, a, b):
tmp = math.exp(a) * math.exp(b)
r = int(math.log(tmp))
return r
(see Natural log and e)
# Solution 3
# Time: O(32)O(32)
# Space: O(1)O(1)
class Solution:
def getSum(self, a: int, b: int) -> int:
# 32 bit mask in hexadecimal
mask = 0xffffffff
# works both as while loop and single value check
while (b & mask) > 0:
carry = ( a & b ) << 1
a = (a ^ b)
b = carry
# handles overflow
return (a & mask) if b > 0 else a
Note 1, this algorithm does not handle the case when it is given a negative b initially. getSum(-7, 3) Ok, getSum(-7,-3) Nope, returns -7. Note 2. We are given the constraint a,b between 1000, -1000, so why accounting for overflow? Negative integers. For using mask here see Masks.
36. (LC 393) UTF-8 Validation
(Medium) Task
Put simply, given a list of integers like [197,130,1], return True if its binary form, here 11000101 10000010 00000001 matches one of the patterns given in the table in the task. In this example it matches (pattern 2 + pattern 1), i.e. True, a valid utf8.
### V my
def valid_utf(a):
bins = [bin(n)[2:].zfill(8) for n in a]
flag = 0
for c in bins[0]:
if c == "0":
break
flag += 1
flag -= 1
for n in bins[1:]:
if n[:2] == "10":
flag -= 1
else:
break
return flag <= 0
data = [197, 130, 1]
data2 = [235, 140, 4]
print(valid_utf(data)) # True
print(valid_utf(data2)) # False
flag -= 1Because the format is:
# Visualization
1 0
2 11 10
3 111 10 10
4 1111 10 10 10
# E.g. flag=2 (11), but only one set of 10.
### Solution
def validUtf8(data):
"""
:type data: List[int]
:rtype: bool
"""
cnt = 0
for d in data:
if cnt == 0:
if (d >> 5) == 0b110:
cnt = 1
elif (d >> 4) == 0b1110:
cnt = 2
elif (d >> 3) == 0b11110:
cnt = 3
elif (d >> 7):
return False
else:
if (d >> 6) != 0b10:
return False
cnt -= 1
return cnt == 0
data1 = [197, 130, 1]
data2 = [235, 140, 1]
print(validUtf8(data1))
print(validUtf8(data2))
# True
# False
Explained:
# This in mind:
1 | 0xxxxxxx
2 | 110xxxxx 10xxxxxx
3 | 1110xxxx 10xxxxxx 10xxxxxx
4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
The algorithm relies on the fact that the first character in data sets the pattern. E.g. if it has that many 1s, then we know that it can match one and only one of the utf patterns, so we iterate throught the remaining patterns knowing how many characters with format 10xxxx we must encounter to make it a valid utf8.
#1
if (d >> 5) == 0b110:
cnt = 1
elif (d >> 4) == 0b1110:
cnt = 2
# Think of the count as the number of more characters the pattern should have.
# E.g. having encountered 0b110, there should be one more item of format 10xxxxx,
# so count=1
2 | 110xxxxx 10xxxxxx
#2
if cnt == 0:..
else:
if (d >> 6) != 0b10:
return False
cnt -= 1
# If count is not 0, then we must have the next character of format 0b10.
# If the next character in data is not 0b10, then the pattern does not match one
# of the utf8 variants. If it is 0b10, we subtract -1.
# If count = 0, then the pattern is complete.
#3
elif (d >> 7):
return False
# If the count is 0 and we encounter anything other than 0xxx, return False.
# I.e. it's ok to encounter 0xxxx after a closed pattern.
### My version with strings
# (I was worried about making sure we deal with 8 bits only.
# But there is really no need. Alg with >> will return False if not 8 bits.)
def f37(a):
pattern = 0
for i in a:
i = (bin(i)[2:]).zfill(8)
print(i)
if pattern == 0:
if i[:5] == '11110':
pattern = 3
elif i[:4] == '1110':
pattern = 2
elif i[:3] == '110':
pattern = 1
elif i[0] == '0':
pattern = 0
else:
return False
elif pattern > 0:
if i[:2] == '10':
pattern -= 1
else:
return False
return pattern == 0
data = [197,130,1]
print(f37(data))
data2 = [235,140,4]
print(f37(data2))
# OUT
# 11000101
# 10000010
# 00000001
# True
# 11101011
# 10001100
# 00000100
# False