Press "Enter" to skip to content

Posts published in “Math”

花花酱 LeetCode 1744. Can You Eat Your Favorite Candy on Your Favorite Day?

You are given a (0-indexed) array of positive integers candiesCount where candiesCount[i] represents the number of candies of the ith type you have. You are also given a 2D array queries where queries[i] = [favoriteTypei, favoriteDayi, dailyCapi].

You play a game with the following rules:

  • You start eating candies on day 0.
  • You cannot eat any candy of type i unless you have eaten all candies of type i - 1.
  • You must eat at least one candy per day until you have eaten all the candies.

Construct a boolean array answer such that answer.length == queries.length and answer[i] is true if you can eat a candy of type favoriteTypei on day favoriteDayi without eating more than dailyCapi candies on any day, and false otherwise. Note that you can eat different types of candy on the same day, provided that you follow rule 2.

Return the constructed array answer.

Example 1:

Input: candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
Output: [true,false,true]
Explanation:
1- If you eat 2 candies (type 0) on day 0 and 2 candies (type 0) on day 1, you will eat a candy of type 0 on day 2.
2- You can eat at most 4 candies each day.
   If you eat 4 candies every day, you will eat 4 candies (type 0) on day 0 and 4 candies (type 0 and type 1) on day 1.
   On day 2, you can only eat 4 candies (type 1 and type 2), so you cannot eat a candy of type 4 on day 2.
3- If you eat 1 candy each day, you will eat a candy of type 2 on day 13.

Example 2:

Input: candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
Output: [false,true,true,false,false]

Constraints:

  • 1 <= candiesCount.length <= 105
  • 1 <= candiesCount[i] <= 105
  • 1 <= queries.length <= 105
  • queries[i].length == 3
  • 0 <= favoriteTypei < candiesCount.length
  • 0 <= favoriteDayi <= 109
  • 1 <= dailyCapi <= 109

Solution: Prefix Sum

  1. We must have enough capacity to eat all candies before the current type.
  2. We must have at least prefix sum candies than days, since we have to eat at least one each day.

sum[i] = sum(candyCount[0~i])
ans = {days * cap > sum[type – 1] && days <= sum[type])

Time complexity:O(n)
Space complexity: O(n)

C++

花花酱 LeetCode 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.

Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.

Example 1:

Input: n = "32"
Output: 3
Explanation: 10 + 11 + 11 = 32

Example 2:

Input: n = "82734"
Output: 8

Example 3:

Input: n = "27346209830709182346"
Output: 9

Constraints:

  • 1 <= n.length <= 105
  • n consists of only digits.
  • n does not contain any leading zeros and represents a positive integer.

Solution: Return the max digit

Proof: For a given string, we find the maximum number m, we create m binary strings.
for each one, check each digit, if it’s greater than 0, we mark 1 at that position and decrease the digit by 1.

e.g. 21534
max is 5, we need five binary strings.
1. 11111: 21534 -> 10423
2. 10111: 10423 -> 00312
3: 00111: 00312 -> 00201
4: 00101: 00201 -> 00100
5: 00100: 00100 -> 00000

We can ignore the leading zeros.

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 1685. Sum of Absolute Differences in a Sorted Array

You are given an integer array nums sorted in non-decreasing order.

Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.

In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).

Example 1:

Input: nums = [2,3,5]
Output: [4,3,5]
Explanation: Assuming the arrays are 0-indexed, then
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.

Example 2:

Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= nums[i + 1] <= 104

Solution: Prefix Sum

Let s[i] denote sum(num[i] – num[j]) 0 <= j <= i
s[i] = s[i – 1] + (num[i] – num[i – 1]) * i
Let l[i] denote sum(nums[j] – nums[i]) i <= j < n
l[i] = l[i + 1] + (nums[i + 1] – num[i]) * (n – i – 1)
ans[i] = s[i] + l[i]

e.g. 1, 3, 7, 9
s[0] = 0
s[1] = 0 + (3 – 1) * 1 = 2
s[2] = 2 + (7 – 3) * 2 = 10
s[3] = 10 + (9 – 7) * 3 = 16
l[3] = 0
l[2] = 0 + (9 – 7) * 1 = 2
l[1] = 2 + (7 – 3) * 2 = 10
l[0] = 10 + (3 – 1) * 3 = 16

ans = [16, 12, 12, 16]

Time complexity: O(n)
Space complexity: O(n)

C++

花花酱 LeetCode 1611. Minimum One Bit Operations to Make Integers Zero

Given an integer n, you must transform it into 0 using the following operations any number of times:

  • Change the rightmost (0th) bit in the binary representation of n.
  • Change the ith bit in the binary representation of n if the (i-1)th bit is set to 1 and the (i-2)th through 0th bits are set to 0.

Return the minimum number of operations to transform n into 0.

Example 1:

Input: n = 0
Output: 0

Example 2:

Input: n = 3
Output: 2
Explanation: The binary representation of 3 is "11".
"11" -> "01" with the 2nd operation since the 0th bit is 1.
"01" -> "00" with the 1st operation.

Example 3:

Input: n = 6
Output: 4
Explanation: The binary representation of 6 is "110".
"110" -> "010" with the 2nd operation since the 1st bit is 1 and 0th through 0th bits are 0.
"010" -> "011" with the 1st operation.
"011" -> "001" with the 2nd operation since the 0th bit is 1.
"001" -> "000" with the 1st operation.

Example 4:

Input: n = 9
Output: 14

Example 5:

Input: n = 333
Output: 393

Constraints:

  • 0 <= n <= 109

Solution 1: Graycode

Time complexity: O(logn)
Space complexity: O(1)

Ans is the order of n in graycode.

C++

花花酱 LeetCode 1588. Sum of All Odd Length Subarrays

Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays.

A subarray is a contiguous subsequence of the array.

Return the sum of all odd-length subarrays of arr.

Example 1:

Input: arr = [1,4,2,5,3]
Output: 58
Explanation: The odd-length subarrays of arr and their sums are:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Example 2:

Input: arr = [1,2]
Output: 3
Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Example 3:

Input: arr = [10,11,12]
Output: 66

Constraints:

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 1000

Solution 0: Brute Force

Enumerate all odd length subarrys: O(n^2), each take O(n) to compute the sum.

Total time complexity: O(n^3)
Space complexity: O(1)

Solution 1: Running Prefix Sum

Reduce the time complexity to O(n^2)

C++

Solution 2: Math

Count how many times arr[i] can be in of an odd length subarray
we chose the start, which can be 0, 1, 2, … i, i + 1 choices
we chose the end, which can be i, i + 1, … n – 1, n – i choices
Among those 1/2 are odd length.
So there will be upper((i + 1) * (n – i) / 2) odd length subarrays contain arr[i]

ans = sum(((i + 1) * (n – i) + 1) / 2 * arr[i] for in range(n))

Time complexity: O(n)
Space complexity: O(1)

C++