Leetcode: Binary and Number Manipulation Flashcards
Binary Operations
&, bitwise AND, x & y, : Returns 1 if both the bits are 1 else 0
a = 10 = 1010 (Binary) b = 4 = 0100 (Binary a & b 1010 & 0100 =0000 =0 (Decimal) Helpful when doing bit addition and you need to know the carry value, x & b << 1 is the carry value
|, bitwise OR, x | y, Bitwise or operator: Returns 1 if either of the bit is 1 else 0.
Example:
a = 10 = 1010 (Binary) b = 4 = 0100 (Binary a | b 1010 | 0100 =1110 =14 (Decimal)
~, bitwise NOT, ~x, Returns one’s compliement of the number
a = 10 = 1010 (Binary)
~a = ~1010
= -(1010 + 1)
= -(1011)
= -11 (Decimal)
https://www.tutorialspoint.com/two-s-complement
^, bitwise XOR, x^y, Returns 1 if one of the bit is 1 and other is 0 else returns false
a = 10 = 1010 (Binary)
b = 4 = 0100 (Binary
https://stackoverflow.com/questions/6398427/what-does-bitwise-xor-exclusive-or-mean
XOR is self-inverting, identity element, and associative
a^(a^b) = b, where b would be f(f(b)) = b
b^a = a^b
XOR’s identity element is 0, X ^ 0 = X for all of X
a & b =
1010
^
0100
= 1110
= 14 (Decimal)
USE CASE: set the last bit of a num to 0, x &= x - 1 : 111 & 110 = 110 = 7, which sets the right most bit to 0
ANOTHER ONE: x % 2 is the same as x & 1. 10 & 01 is 0, even. 11 & 01 is 1, which means odd
> > , bitwise right shift, x»y, shifts the bits “away” from the number, dividing it by 2, or multiplying it by (1/2)^y, floor division too, no floats in binary!
This makes sense bc we shift the binary values 1 to the left or right, that takes away or adds a binary value, which will effectively DOUBLE or HALF the amount of values we can have, therefore doubling or halfing the the value
a=12=1100 a>>1 = 110, = 6 a>>2 = 11, =3 a>>3=1, =1 a>>4=0=0
list strategies for binary
- when in doubt, XOR
- > > 1 halfs, «_space;1 doubles
- exponential search when you are not allowed to use multiplication/division/modulus
kth grammar (can not be binary)
We build a table of n rows (1-indexed). We start by writing 0 in the 1st row. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.
For example, for n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.
Given two integer n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.
Example 1:
Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0
Example 2:
Input: n = 2, k = 1 Output: 0 Explanation: row 1: 0 row 2: 01 Example 3:
Input: n = 2, k = 2 Output: 1 Explanation: row 1: 0 row 2: 01
brute is quadratic time and 2^n space, double for loop and the space is squared after each row
- —def brute(self, n, k):
- ——-prev=’0’
- ——-c=[]
- ——-for i in range(1, n):
- ———–for s in prev:
- —————if s==’0’:
- ——————-c.extend([‘0’, ‘1’])
- —————elif s==’1’:
- ——————-c.extend([‘1’, ‘0’])
- ———–prev=’‘.join(c)
- ———–c=[]
- ——-return prev[k-1]
- draw solution, see if you can find a pattern
- 0, 01, 0110, 01101001
- next row is extending the compliment of previous
- if we want k=5 (index at 1) at n=4, we get 1. is there a way to work backwards?
- the index at 5 was spawned from the previous index at 3, the index at 6 also came from 3. the parent is 1, index at 5 is 1, index at 6 is 0. If the parent was 0, we have the reverse
- depending on the kth value and the parent value, we can what the output will be!
- we to solve n=4, k=5, we need to know the value of the parent plus if k is an odd or even index
- 5 and 6 evaluate to 3, so we need to do round up floor division (k//2+k%2)
- base case is if n=1, we have the row 0, so the parent is 0
time: O(n log(n)) because we do this n times and the modulus operator is logN time
space: recursive stack space is linear with N
class Solution:
- —def kthGrammar(self, n, k):
- ——-if n==1: return 0
- ——-parent = self.kthGrammar(n-1, k//2+k%2)
- ——-odd=(k%2==1)
- ——-if parent==1:
- ———–return 1 if odd else 0
- ——-else:
- ———–return 0 if odd else 1
add binary
Given two binary strings a and b, return their sum as a binary string.
Example 1:
Input: a = “11”, b = “1”
Output: “100”
Example 2:
Input: a = “1010”, b = “1011”
Output: “10101”
brute is to convert the strings to ints using int(x, 2) to represent a base 2 system, then add them, format back to binary. Time/space is O(n+m) bc we need to operate both inputs and hold both in space
def brute(self, a, b): ----return bin((int(a, 2) + int(b, 2)))[2:]
- XOR, when in doubt, XOR. See that you can convert string bits into regular ints, then it is the same as the binary addition problem. We do not need to worry which is greater bc XOR is an identify function
- carry is x & b «_space;1 ,will give you the carry value for binary purposes
- x = a^b, carry = a&b «_space;1, as long as carry is not 0, continue with x ^ carry, and repeat
- make sure the while loop is on the carry variable, bc once that is 0, x ^ 0 = x, so we are done, it is the identity function of XOR
time: O(n+m) bc we have to convert them to ints, the XOR part is O(32) bc we are using 32 bit ints
space: O(max(n,m)) bc we need to store the answer
- —def addBinary(self, a: str, b: str) -> str:
- ——-x, y = int(a, 2), int(b, 2)
- ——-while y:
- ———–answer = x ^ y
- ———–carry = (x & y) «_space;1
- ———–x, y = answer, carry
- ——-return bin(x)[2:]
- realize we need a carry, zfill, if you don’t know zfill just do it like mergesort
- modulus is important bc 3%2 and 1%2 cover the same situation, add 1, but then floor division will let us know if we have a carry value
time: O (max(n, m) bc we only operate based on the largest input
space: O(A + B + answer) since we store A, B, and the answer in memory
from collections import deque
class Solution:
----def addBinary1(self, a: str, b: str) -> str:
--------n = max(len(a), len(b))
--------a, b = a.zfill(n), b.zfill(n)
--------out = deque()
--------carry = 0
--------for i in range(n - 1, -1, -1):
------------x = int(a[i])
------------y = int(b[i])
------------current = x + y + carry
------------
------------if current % 2 == 1:
----------------out.appendleft("1")
------------else:
----------------out.appendleft("0")
------------carry = current // 2
--------if carry == 1:
------------out.appendleft("1")
--------return "".join(out)
single number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
brute force would be the math, since each value is is there twice except our answer, take the set, multiply by 2, and subtract from the sum of original set you get the single number
- XOR identity elemty, x^b^x = b, bc x^x = 0, and x^0 = x
time: linear
space: constant
class Solution:
- ——-ans = nums[0]
- ——-for i in range(1, len(nums)):
- ———–ans = ans ^ nums[i]
- ——-return ans
- —def math(self, nums):
- ——-return 2*sum(set(nums)) - sum(nums)
Sum of two integers
Given two integers a and b, return the sum of the two integers without using the operators + and -.
Example 1:
Input: a = 1, b = 2
Output: 3
Example 2:
Input: a = 2, b = 3
Output: 5
time: O(32), constant since there are only 32 bits
space: O(32), constant since there are only 32 bits and we dont make any new data structures
- for the addition of 2 numbers that are both positive/negative, the order doesnt matter, it only matters for when the signs are opposite for subtraction purposes
- it also matters which is larger so we can determine the final sign. If the largest value is still negative, final sign will be negative, else, it will be positive
- check if a is negative, check if both are negative, that is why we have so many different if statements to figure all this out
- addition is simple, XOR and & «_space;1, check to make sure carry is not 0, if it is return the answer
- subtraction we need to make sure the largest number is not the borrow, if it is than we make an infinite loop
class SumOfTwoBinary(object):
- —def answer1(self, a, b):
- ——-x, y = abs(a), abs(b)
- ——-if x[less than]y:
- ———–x,y = y, x
- ———–a,b = b, a
- ——-# sign = 1 if a[greater than]0 else -1
- ——-if a[greater than]0:
- ———–sign=1
- ——-else:
- ———–sign=-1
- ——-if a*b[greater than]=0:
- ———–while y:
- —————answer=x^y
- —————borrow = (x&y)[less than][less than]1
- —————x,y = answer, borrow
- ——-else:
- ———–while y:
- —————answer = x^y
- —————carry = ((~x)&y)[less than][less than]1
- —————x, y = answer, carry
- ——-return x*sign
divide 2 integers
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, assume that your function returns 231 − 1 when the division result overflows.
brute force is to add the divisor until you cant anymore, then get the answer. That is linear but is also really bad incase of large dividends
- exponential search
- same idea as brute, but we scale up exponentially, then when we are too large, we scale down
- use the right shift operators to reduce the current value and the power
- you can use memoization to keep of the previous values during exponential search and then search backwards through them (you would need 1 list for the power, 1 list for the values)
- step 4 is unnecessary, you can do it manually without the memos
time: O(log(n)), exponential search is logN time
space: logN if you have the memos, constant if you do not
class Solution:
- —def memo(self, dividend: int, divisor: int) -[greater than] int:
- ——-powers = []
- ——-values = []
- ——-max_int = 2**31 -1
- ——-min_int = -2**31
- ——-half = -1073741824 # can’t use division
- ——-if dividend == min_int and divisor == -1:
- ———–return max_int
- ——-negatives = 2
- ——-if dividend [greater than] 0:
- ———–negatives -= 1
- ———–dividend = -dividend
- ——-if divisor [greater than] 0:
- ———–negatives -= 1
- ———–divisor = -divisor
- ——-quotient = 0
- ——-power = -1
- ——-value = divisor
- ——-while divisor [greater than]= dividend:
- ———–values.append(value)
- ———–powers.append(power)
- ———–if half [greater than] value:
- —————break
- ———–value += value
- ———–power += power
- ——-for i in range(len(values)-1, -1, -1):
- ———–if values[i] [greater than]= dividend:
- —————quotient += powers[i]
- —————dividend -= values[i]——–
- ——-return quotient if negatives is 1 else -quotient
time: log(n)
space: constant
class Solution:
- —def divide(self, dividend: int, divisor: int) -[greater than] int:
- ——-max_int = 2**31 -1
- ——-min_int = -2**31
- ——-half = -1073741824 # can’t use division
- ——-if dividend == min_int and divisor == -1:
- ———–return max_int
- ——-negatives = 2
- ——-if dividend [greater than] 0:
- ———–negatives -= 1
- ———–dividend = -dividend
- ——-if divisor [greater than] 0:
- ———–negatives -= 1
- ———–divisor = -divisor
- ——-if dividend [greater than] divisor:
- ———–return 0
- ——-quotient = 0
- ——-power = -1
- ——-value = divisor
- ——-# negative values
- ——-while value [greater than]= half and value + value [greater than]= dividend:
- ———–value += value
- ———–power += power
- ——-while divisor [greater than]= dividend:
- ———–if value [greater than]= dividend:
- —————quotient += power
- —————dividend -= value
- ———–power = (power [greater than][greater than] 1)
- ———–value = (value [greater than][greater than] 1)
- ——-return quotient if negatives is 1 else -quotient
missing element
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
- know Gauss sum, or binary manipluation
- for Gauss sum, since the sumation equation is inclusive on N, we use the len(nums) bc that gives us gauss sum from 0 to n-1, which n-1 = len(nums)
- binary, you use len(nums) too. you need to right out len nums, range of nums, nums in the arr, then cancel them out manually bc you know 1^1 = 0. below you should be able to see if you start by xor the index + value against the len, you will find the missing item
len(nums) = 3
range: 0 1 2
values: 3 0 1
time: O(n)
space: constant
class Solution:
- —def missingNumber(self, nums):
- ——-# Gauss’ formula, sum(0, n) inclusive of n
- ——-total = (len(nums) * (len(nums) + 1)) // 2
- ——-actual = sum(nums)
- ——-return total - actual
- —def good_binary(self, nums):
- ——-ans = len(nums)
- ——-for i in range(len(nums)):
- ———–y = i ^ nums[i]
- ———–ans ^= y
- ——-return ans
- —#takes up N space
- —def bad_binary(self, nums):
- ——-nums.append(0)
- ——-ans = 0
- ——-for i in range(len(nums)):
- ———–y = i ^ nums[i]
- ———–ans ^= y
- ——-return ans
happy number
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
Input: n = 19 Output: true Explanation: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1 Example 2:
Input: n = 2
Output: false
- you need to know all numbers converge around 243 in a cycle or to 1. the largest number a 13 digit number could give us is 1053, which goes to 35, this is true for larger numbers too
- it ends if we find n == 1 or we have a cycle. we can find a cycle using a hashmap, which can be optimized to O(243) time by rejecting any adds above 243, since we can’t really get back to them anyway, or use floyd’s cycle finding algo with a fast/slow pointer
time: O(log(n)), this is tricky, it requires us to know that we cycle around 243, and it takes log(n) time to perform the happy calculation because it is based on the digits in the number, which is on a base-10 system so log(n). For numbers larger thatn 243, it will take log(log(log(n))) time, which basically means log(n)
space: O(1) or O(243) if we do an optimized hashmap
class Solution:
- —def isHappy(self, n: int) -> bool:
- ——-seen = set()
- ——-while n != 1 and n not in seen:
- ———–seen.add(n)
- ———–n = self.new_n(n)
- ——-return n == 1
- —def new_n(self, n):
- ——-new = 0
- ——-while n > 0:
- ———–div, mod = divmod(n, 10)
- ———–new += mod ** 2
- ———–n = div
- ——-return new
Solution2
- —def isHappy_floyds_cycle(self, n: int) -> bool:
- ——-slow = n
- ——-fast = self.new_n(n)
- ——-while slow != 1 and slow != fast:
- ———–slow = self.new_n(slow)
- ———–fast = self.new_n(self.new_n(fast))
- ——-return slow == 1
- —def new_n(self, n):
- ——-new = 0
- ——-while n > 0:
- ———–div, mod = divmod(n, 10)
- ———–new += mod ** 2
- ———–n = div
- ——-return new
- Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).
Note:
Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3.
Example 1:
Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three ‘1’ bits.
time: O(32), space is O(1). On LC it says that the time is O(1), but then it references that the worst case is 32 1’s. Make sure to clarify this worst-case scenario and just say it is constant in an interview
class Solution:
- —def hammingWeight(self, n):
- ——-bits = 0
- ——-temp = 1
- ——-for _ in range(32):
- ———–if ((n & temp) != 0):
- —————bits += 1
- ———–temp = temp «_space;1
- ——-return bits
time: O(32) space/time, since the string could take up 32 bits
- —def pythonic(self, n):
- ——-return bin(n).count(“1”)
time/space: O(32) / O(1)
—-def bit_manipulation2(self, n):
——–bits = 0
——–’’’
110011 &= 110010 = 110010 add 1
110010 &= 110001 = 110000 adds 1
110000 &= 101111 = 100000 adds 1
100000 &= 011111 = 000000 adds 1, result is 4, crazy this works
‘’’
——–while n > 0:
————bits += 1
————n &= (n -1)
——–return bits
- Counting Bits
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.
Example 1:
Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10
time: O(n * 32), worst case for each N is 32 bc of how many bits are in a 32 int
space: O(1), not including answer
class Solution:
- —def countBits(self, n):
- ——-response = []
- ——-for i in range(n + 1):
- ———–num = i
- ———–bits = 0
- ———–while num > 0:
- —————bits += 1
- —————num &= (num - 1)
- ———–response.append(bits)
- ——-return response
- if x is 4, x // 2 = 2, which has the same number of 1-bits + 1 if it is odd, 0 if it is even
- this gives us response[i] = response[i»_space; 1] + (i & 1), i & 1 is th same as i % 2, crazy right
- use the DP array to calculate previous values
time: O(n), we loop through n once
space: O(1), not including answer
- —# bit wise problems fucking suck, idk how you can just figure this out wtf
- —def dp_lsb(self, n):
- ——-response = [0] * (n + 1)
- ——-for i in range(1, n + 1):
- ———–response[i] = response[i»_space; 1] + (i & 1)
- ——-return response
- memorize, you have to know using a [0] dp array and x & (x-1), at each x it brings you back to a previous value in the dp array that you need. Then you just add 1 to that value
time: O(n), we loop through n once
space: O(1), not including answer
- —# lsb/msb is least/most significant bit. msb is usually whether or not it is negative or not
- —def dp_last_set_bit(self, n):
- ——-response = [0] * (n + 1)
- ——-for i in range(1, n + 1):
- ———–response[i] = response[i & (i - 1)] + 1
- ——-return response
- Count Primes
Given an integer n, return the number of prime numbers that are strictly less than n.
Example 1:
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
- memorize. this solution, its fucking dumb math formula
- start with 2, add each multiple above 2 to the map, continue upwards. any number not in the map is a prime number
- N and 1 are not prime numbers, so for a given N we subtract 2 initially, then subtract all the non-primes (len of map)
time: O(squareroot(n) * log(log(n)) ): logN because we go from base*base, n, base, then log(log(n)) bc we keep increaseing the base value over each iteration. there is a proof somewhere, square root N * log n is probably correct too space O(N): we can store n values in the hashmap
time:
class Solution:
—-def countPrimes(self, n: int) -> int:
——–if n <= 2:
————return 0
——–
——–composite_nums = {}
——–square_root = int(n ** 0.5)
——–for base in range(2, square_root + 1):
————if base not in composite_nums:
—————-for multiple in range(base*base, n, base):
——————–composite_nums[multiple] = 1
——–
——–return n - 2 - len(composite_nums)
