Find the largest 3^x that <= n, subtract that from n and repeat the process. x should be monotonically decreasing, otherwise we have duplicate terms. e.g. 12 = 32 + 31 true e.g. 21 = 32 + 32+ 31 false
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 themaximumscore 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++
1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution{
public:
intmaximumScore(inta,intb,intc){
array<int,3>s{a,b,c};
sort(begin(s),end(s));
intans=0;
while(s[1]--&& s[2]--) {
++ans;
sort(begin(s),end(s));
}
returnans;
}
};
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
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 leastone 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 thandailyCapi 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.
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 ymust 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)
Given ncuboids 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 stackedcuboids.
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.
