Press "Enter" to skip to content

Posts tagged as “math”

花花酱 LeetCode 1753. Maximum Score From Removing Stones

You are playing a solitaire game with three piles of stones of sizes a​​​​​​, b,​​​​​​ and c​​​​​​ respectively. Each turn you choose two different non-empty piles, take one stone from each, and add 1 point to your score. The game stops when there are fewer than two non-empty piles (meaning there are no more available moves).

Given three integers a​​​​​, b,​​​​​ and c​​​​​, return the maximum score you can get.

Example 1:

Input: a = 2, b = 4, c = 6
Output: 6
Explanation: The starting state is (2, 4, 6). One optimal set of moves is:
- Take from 1st and 3rd piles, state is now (1, 4, 5)
- Take from 1st and 3rd piles, state is now (0, 4, 4)
- Take from 2nd and 3rd piles, state is now (0, 3, 3)
- Take from 2nd and 3rd piles, state is now (0, 2, 2)
- Take from 2nd and 3rd piles, state is now (0, 1, 1)
- Take from 2nd and 3rd piles, state is now (0, 0, 0)
There are fewer than two non-empty piles, so the game ends. Total: 6 points.

Example 2:

Input: a = 4, b = 4, c = 6
Output: 7
Explanation: The starting state is (4, 4, 6). One optimal set of moves is:
- Take from 1st and 2nd piles, state is now (3, 3, 6)
- Take from 1st and 3rd piles, state is now (2, 3, 5)
- Take from 1st and 3rd piles, state is now (1, 3, 4)
- Take from 1st and 3rd piles, state is now (0, 3, 3)
- Take from 2nd and 3rd piles, state is now (0, 2, 2)
- Take from 2nd and 3rd piles, state is now (0, 1, 1)
- Take from 2nd and 3rd piles, state is now (0, 0, 0)
There are fewer than two non-empty piles, so the game ends. Total: 7 points.

Example 3:

Input: a = 1, b = 8, c = 8
Output: 8
Explanation: One optimal set of moves is to take from the 2nd and 3rd piles for 8 turns until they are empty.
After that, there are fewer than two non-empty piles, so the game ends.

Constraints:

  • 1 <= a, b, c <= 105

Solution 1: Greedy

Take two stones (one each) from the largest two piles, until one is empty.

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

C++

Solution 2: Math

First, let’s assuming a <= b <= c.
There are two conditions:
1. a + b <= c, we can pair c with a first and then b. Total pairs is (a + b + (a + b)) / 2
2. a + b > c, we can pair c with a, b “evenly”, and then pair a with b, total pairs is (a + b + c) / 2

ans = (a + b + min(a + b, c)) / 2

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

C++

花花酱 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 1739. Building Boxes

You have a cubic storeroom where the width, length, and height of the room are all equal to n units. You are asked to place n boxes in this room where each box is a cube of unit side length. There are however some rules to placing the boxes:

  • You can place the boxes anywhere on the floor.
  • If box x is placed on top of the box y, then each side of the four vertical sides of the box y must either be adjacent to another box or to a wall.

Given an integer n, return the minimum possible number of boxes touching the floor.

Example 1:

Input: n = 3
Output: 3
Explanation: The figure above is for the placement of the three boxes.
These boxes are placed in the corner of the room, where the corner is on the left side.

Example 2:

Input: n = 4
Output: 3
Explanation: The figure above is for the placement of the four boxes.
These boxes are placed in the corner of the room, where the corner is on the left side.

Example 3:

Input: n = 10
Output: 6
Explanation: The figure above is for the placement of the ten boxes.
These boxes are placed in the corner of the room, where the corner is on the back side.

Constraints:

  • 1 <= n <= 109

Solution: Geometry

Step 1: Build a largest pyramid that has less then n cubes, whose base area is d*(d+1) / 2
Step 2: Build a largest triangle with cubes left, whose base area is l, l*(l + 1) / 2 >= left

Time complexity: O(n^(1/3))
Space complexity: O(1)

C++

花花酱 LeetCode 1691. Maximum Height by Stacking Cuboids

Given n cuboids where the dimensions of the ith cuboid is cuboids[i] = [widthi, lengthi, heighti] (0-indexed). Choose a subset of cuboids and place them on each other.

You can place cuboid i on cuboid j if widthi <= widthj and lengthi <= lengthj and heighti <= heightj. You can rearrange any cuboid’s dimensions by rotating it to put it on another cuboid.

Return the maximum height of the stacked cuboids.

Example 1:

Input: cuboids = [[50,45,20],[95,37,53],[45,23,12]]
Output: 190
Explanation:
Cuboid 1 is placed on the bottom with the 53x37 side facing down with height 95.
Cuboid 0 is placed next with the 45x20 side facing down with height 50.
Cuboid 2 is placed next with the 23x12 side facing down with height 45.
The total height is 95 + 50 + 45 = 190.

Example 2:

Input: cuboids = [[38,25,45],[76,35,3]]
Output: 76
Explanation:
You can't place any of the cuboids on the other.
We choose cuboid 1 and rotate it so that the 35x3 side is facing down and its height is 76.

Example 3:

Input: cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
Output: 102
Explanation:
After rearranging the cuboids, you can see that all cuboids have the same dimension.
You can place the 11x7 side down on all cuboids so their heights are 17.
The maximum height of stacked cuboids is 6 * 17 = 102.

Constraints:

  • n == cuboids.length
  • 1 <= n <= 100
  • 1 <= widthi, lengthi, heighti <= 100

Solution: Math/Greedy + DP

Direct DP is very hard, since there is no orders.

We have to find some way to sort the cuboids such that cuboid i can NOT stack on cuboid j if i > j. Then dp[i] = max(dp[j]) + height[i], 0 <= j < i, for each i, find the best base j and stack on top of it.
ans = max(dp)

We can sort the cuboids by their sorted dimensions, and cuboid i can stack stack onto cuboid j if and only if w[i] <= w[j] and l[i] <= l[j] and h[i] <= h[j].

First of all, we need to prove that all heights must come from the largest dimension of each cuboid.

1. If the top of the stack is A1*A2*A3, A3 < max(A1, A2), we can easily swap A3 with max(A1, A2), it’s still stackable but we get larger heights.
e.g. 3x5x4, base is 3×5, height is 4, we can rotate to get base of 3×4 with height of 5.

2. If a middle cuboid A of size A1*A2*A3, assuming A1 >= A2, A1 > A3, on top of A we have another cuboid B of size B1*B2*B3, B1 <= B2 <= B3.
We have A1 >= B1, A2 >= B2, A3 >= B3, by rotating A we have A3*A2*A1
A3 >= B3 >= B1, A2 >= B2, A1 > A3 >= B3, so B can be still on top of A, and we get larger height.

e.g. A: 3x5x4, B: 2x3x4
A -> 3x4x5, B is still stackable.

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

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++