Huahua’s Tech Road

花花酱 LeetCode 1742. Maximum Number of Balls in a Box

By zxi on January 30, 2021

You are working in a ball factory where you have n balls numbered from lowLimit up to highLimit inclusive (i.e., n == highLimit - lowLimit + 1), and an infinite number of boxes numbered from 1 to infinity.

Your job at this factory is to put each ball in the box with a number equal to the sum of digits of the ball’s number. For example, the ball number 321 will be put in the box number 3 + 2 + 1 = 6 and the ball number 10 will be put in the box number 1 + 0 = 1.

Given two integers lowLimit and highLimit, return the number of balls in the box with the most balls.

Example 1:

Input: lowLimit = 1, highLimit = 10
Output: 2
Explanation:
Box Number:  1 2 3 4 5 6 7 8 9 10 11 ...
Ball Count:  2 1 1 1 1 1 1 1 1 0  0  ...
Box 1 has the most number of balls with 2 balls.

Example 2:

Input: lowLimit = 5, highLimit = 15
Output: 2
Explanation:
Box Number:  1 2 3 4 5 6 7 8 9 10 11 ...
Ball Count:  1 1 1 1 2 2 1 1 1 0  0  ...
Boxes 5 and 6 have the most number of balls with 2 balls in each.

Example 3:

Input: lowLimit = 19, highLimit = 28
Output: 2
Explanation:
Box Number:  1 2 3 4 5 6 7 8 9 10 11 12 ...
Ball Count:  0 1 1 1 1 1 1 1 1 2  0  0  ...
Box 10 has the most number of balls with 2 balls.

Constraints:

1 <= lowLimit <= highLimit <= 10⁵

Solution: Hashtable and base-10

Max sum will be 9+9+9+9+9 = 45

Time complexity: O((hi-lo) * log(hi))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countBalls(int lowLimit, int highLimit) {

vector<int> balls(46);

int ans = 0;

for (int i = lowLimit; i <= highLimit; ++i) {

int n = i;

int box = 0;

while (n) { box += n % 10; n /= 10; }

ans = max(ans, ++balls[box]);

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def countBalls(self, lowLimit: int, highLimit: int) -> int:

balls = defaultdict(int)

ans = 0

for x in range(lowLimit, highLimit + 1):

s = sum(int(d) for d in str(x))

balls[s] += 1

ans = max(ans, balls[s])

return ans

花花酱 LeetCode 1739. Building Boxes

By zxi on January 23, 2021

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 <= 10⁹

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

// Author: Huahua

class Solution {

public:

int minimumBoxes(int n) {

int d = 0;

int l = 0;

while (n - (d + 1) * (d + 2) / 2 > 0) {

n -= (d + 1) * (d + 2) / 2;

++d;

}

while (n > 0) n -= ++l;

return d * (d + 1) / 2 + l;

}

};

花花酱 LeetCode 1738. Find Kth Largest XOR Coordinate Value

By zxi on January 23, 2021

You are given a 2D matrix of size m x n, consisting of non-negative integers. You are also given an integer k.

The value of coordinate (a, b) of the matrix is the XOR of all matrix[i][j] where 0 <= i <= a < m and 0 <= j <= b < n (0-indexed).

Find the k^th largest value (1-indexed) of all the coordinates of matrix.

Example 1:

Input: matrix = [[5,2],[1,6]], k = 1
Output: 7
Explanation: The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.

Example 2:

Input: matrix = [[5,2],[1,6]], k = 2
Output: 5
Explanation: The value of coordinate (0,0) is 5 = 5, which is the 2nd largest value.

Example 3:

Input: matrix = [[5,2],[1,6]], k = 3
Output: 4
Explanation: The value of coordinate (1,0) is 5 XOR 1 = 4, which is the 3rd largest value.

Example 4:

Input: matrix = [[5,2],[1,6]], k = 4
Output: 0
Explanation: The value of coordinate (1,1) is 5 XOR 2 XOR 1 XOR 6 = 0, which is the 4th largest value.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
0 <= matrix[i][j] <= 10⁶
1 <= k <= m * n

Solution: DP

xor[i][j] = matrix[i][j] ^ xor[i – 1][j – 1] ^ xor[i – 1][j] ^ xor[i][j- 1]

Time complexity: O(mn)
Space complexity: O(mn)

C++

// Author: Huahua

class Solution {

public:

int kthLargestValue(vector<vector<int>>& matrix, int k) {

const int m = matrix.size(), n = matrix[0].size();

vector<int> v;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

v.push_back(matrix[i][j]

^= (i ? matrix[i - 1][j] : 0)

^ (j ? matrix[i][j - 1] : 0)

^ (i * j ? matrix[i - 1][j - 1] : 0));

nth_element(begin(v), begin(v) + k - 1, end(v), greater<int>());

return v[k - 1];

}

};

花花酱 LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions

By zxi on January 23, 2021

You are given two strings a and b that consist of lowercase letters. In one operation, you can change any character in a or b to any lowercase letter.

Your goal is to satisfy one of the following three conditions:

Every letter in a is strictly less than every letter in b in the alphabet.
Every letter in b is strictly less than every letter in a in the alphabet.
Both a and b consist of only one distinct letter.

Return the minimum number of operations needed to achieve your goal.

Example 1:

Input: a = "aba", b = "caa"
Output: 2
Explanation: Consider the best way to make each condition true:
1) Change b to "ccc" in 2 operations, then every letter in a is less than every letter in b.
2) Change a to "bbb" and b to "aaa" in 3 operations, then every letter in b is less than every letter in a.
3) Change a to "aaa" and b to "aaa" in 2 operations, then a and b consist of one distinct letter.
The best way was done in 2 operations (either condition 1 or condition 3).

Example 2:

Input: a = "dabadd", b = "cda"
Output: 3
Explanation: The best way is to make condition 1 true by changing b to "eee".

Constraints:

1 <= a.length, b.length <= 10⁵
a and b consist only of lowercase letters.

Solution: Brute Force

Time complexity: O(26*(m+n))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minCharacters(string a, string b) {

auto change = [](const string& a, const string& b) {

int ans = INT_MAX;

for (char c = 'a'; c < 'z'; ++c) {

int ops = 0;

for (char x : a) ops += x > c;

for (char x : b) ops += x <= c;

ans = min(ans, ops);

}

return ans;

};

int ans = min(change(a, b), change(b, a));

for (char c = 'a'; c <= 'z'; ++c) {

int ops = a.size() - count(begin(a), end(a), c) +

b.size() - count(begin(b), end(b), c);

ans = min(ans, ops);

}

return ans;

}

};

花花酱 LeetCode 1736. Latest Time by Replacing Hidden Digits

By zxi on January 23, 2021

You are given a string time in the form of hh:mm, where some of the digits in the string are hidden (represented by ?).

The valid times are those inclusively between 00:00 and 23:59.

Return the latest valid time you can get from time by replacing the hidden digits.

Example 1:

Input: time = "2?:?0"
Output: "23:50"
Explanation: The latest hour beginning with the digit '2' is 23 and the latest minute ending with the digit '0' is 50.

Example 2:

Input: time = "0?:3?"
Output: "09:39"

Example 3:

Input: time = "1?:22"
Output: "19:22"

Constraints:

time is in the format hh:mm.
It is guaranteed that you can produce a valid time from the given string.

Solution 1: Brute Force

Enumerate all possible clock in reverse order and find the first matching one.

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

C++

// Author: Huahua

class Solution {

public:

string maximumTime(string time) {

for (int m = 60 * 24 - 1; m >= 0; --m) {

int hh = m / 60;

int mm = m % 60;

if (time[0] != '?' && time[0] - '0' != hh / 10) continue;

if (time[1] != '?' && time[1] - '0' != hh % 10) continue;

if (time[3] != '?' && time[3] - '0' != mm / 10) continue;

if (time[4] != '?' && time[4] - '0' != mm % 10) continue;

time[0] = (hh / 10) + '0';

time[1] = (hh % 10) + '0';

time[3] = (mm / 10) + '0';

time[4] = (mm % 10) + '0';

break;

}

return time;

}

};

Solution 2: Rules

Using rules, fill from left to right.

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

C++

// Author: Huahua

class Solution {

public:

string maximumTime(string time) {

if (time[0] == '?') time[0] = time[1] >= '4' && time[1] <= '9' ? '1' : '2';

if (time[1] == '?') time[1] = time[0] == '2' ? '3' : '9';

if (time[3] == '?') time[3] = '5';

if (time[4] == '?') time[4] = '9';

return time;

}

};

Huahua's Tech Road

花花酱 LeetCode 1742. Maximum Number of Balls in a Box

Solution: Hashtable and base-10

C++

Python3

花花酱 LeetCode 1739. Building Boxes

Solution: Geometry

C++

花花酱 LeetCode 1738. Find Kth Largest XOR Coordinate Value

Solution: DP

C++

花花酱 LeetCode 1737. Change Minimum Characters to Satisfy One of Three Conditions

Solution: Brute Force

C++

花花酱 LeetCode 1736. Latest Time by Replacing Hidden Digits

Solution 1: Brute Force

C++

Solution 2: Rules

C++