Math Flashcards
https://leetcode.com/problems/smallest-missing-non-negative-integer-after-operations/description/
- Smallest Missing Non-negative Integer After Operations
Hard
Companies: Atlassian
You are given a 0-indexed integer array nums and an integer value.
In one operation, you can add or subtract value from any element of nums.
For example, if nums = [1,2,3] and value = 2, you can choose to subtract value from nums[0] to make nums = [-1,2,3].
The MEX (minimum excluded) of an array is the smallest missing non-negative integer in it.
For example, the MEX of [-1,2,3] is 0 while the MEX of [1,0,3] is 2.
Return the maximum MEX of nums after applying the mentioned operation any number of times.
Example 1:
Input: nums = [1,-10,7,13,6,8], value = 5
Output: 4
Explanation: One can achieve this result by applying the following operations:
- Add value to nums[1] twice to make nums = [1,0,7,13,6,8]
- Subtract value from nums[2] once to make nums = [1,0,2,13,6,8]
- Subtract value from nums[3] twice to make nums = [1,0,2,3,6,8]
The MEX of nums is 4. It can be shown that 4 is the maximum MEX we can achieve.
Example 2:
Input: nums = [1,-10,7,13,6,8], value = 7
Output: 2
Explanation: One can achieve this result by applying the following operation:
- subtract value from nums[2] once to make nums = [1,-10,0,13,6,8]
The MEX of nums is 2. It can be shown that 2 is the maximum MEX we can achieve.
Constraints:
1 <= nums.length, value <= 105
-109 <= nums[i] <= 109
https://leetcode.com/problems/smallest-missing-non-negative-integer-after-operations/description/
Check https://leetcode.com/problems/smallest-missing-non-negative-integer-after-operations/solutions/3313988/count-moduli/ why this works.
Basically perfect list will be 0,1,2,3,4 thus mex has to be 5 since that is the smallest missing non negative integer.
eg of imperfect list [0,0,1,1,2,2,3,3,4,4] value 5 - This does contain all numbers from 0-4, but we want maximum mex. We can say mex is 5 but that won’t be the maximum mex. as we can modify each number once (since it’s availble 2 times) to artificially increase the values in the list. eg
thus for each modulo we have 2 numbers eg 0-2, 1-2, 2-2, 3-2, 4-2
[0,1,2,3,4,5,6,7,8,9] - all we did was add 5 one time to all elements now we have this list, for this mex is 10, we can’t go higher than that. (you can try and see), as if we modify the original small elements one time then we lose the lower boundary and we get a smaller mex.
Mainly we are trying to create the tighest boundary possible.
for list like [0,1,8], value 3
We leave 0 as it is, as it gives us a lower bound, then 1, we leave it as is, since it gives us lower bound, now we have 2-6 as possible mex candidates.
how can we tighten the boundary here? we can’t increment 1 so we reduce 8 to 2,
this makes the mex candidates 3 and above since now there is no upper bound, we take the lowest bound and return.
https://leetcode.com/problems/missing-ranges/description/
This is useful problem to understand here.
The missing ranges are the mex candidates.
from collections import Counter
class Solution:
def findSmallestInteger(self, nums: List[int], value: int) -> int:
nmod_counter = Counter(map(lambda n: n%value, nums))
for i in range(len(nums)):
if nmod_counter[i%value] == 0:
return i
else:
nmod_counter[i%value] -= 1
# else return len of the list because at this point the list is perfect ie. 0,1,2,3,4,5 so the mex has to be 6
return len(nums)
- Random Pick with Weight
Solved
Medium
Topics
Companies
You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.
You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).
For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).
Example 1:
Input
[“Solution”,”pickIndex”]
[[[1]],[]]
Output
[null,0]
Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
Example 2:
Input
[“Solution”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]
Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.
Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
……
and so on.
Constraints:
1 <= w.length <= 104
1 <= w[i] <= 105
pickIndex will be called at most 104 times.
import random
from itertools import accumulate
class Solution(object):
def \_\_init\_\_(self, w):
"""
:type w: List[int]
"""
self.w = w
self.total_sum = sum(w)
self.prefix_sum = list(accumulate(self.w))
def pickIndex(self):
"""
:rtype: int
"""
frac = random.random()
idx = bisect.bisect_left(self.prefix_sum, self.total_sum * frac)
return idx
Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()
