Leetcode: Binary and Number Manipulation Flashcards

Question 1

Q

Binary Operations

Answer

A

&, 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

Question 2

Q

list strategies for binary

Answer

A

when in doubt, XOR
> > 1 halfs, «_space;1 doubles
exponential search when you are not allowed to use multiplication/division/modulus

Question 3

Q

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

Answer

A

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

Question 4

Q

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”

Answer

A

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)

Question 5

Q

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

Answer

A

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)

Question 6

Q

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

Answer

A

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

Question 7

Q

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.

Answer

A

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

Question 8

Q

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.

Answer

A

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

Question 9

Q

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

Answer

A

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

Question 10

Q

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.

Answer

A

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

Question 11

Q

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

Answer

A

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

Question 12

Q

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.

Answer

A

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)

Leetcode: Binary and Number Manipulation Flashcards

(12 cards)