Press "Enter" to skip to content

Posts tagged as “math”

LeetCode 2033. Minimum Operations to Make a Uni-Value Grid

You are given a 2D integer grid of size m x n and an integer x. In one operation, you can add x to or subtract x from any element in the grid.

uni-value grid is a grid where all the elements of it are equal.

Return the minimum number of operations to make the grid uni-value. If it is not possible, return -1.

Example 1:

Input: grid = [[2,4],[6,8]], x = 2
Output: 4
Explanation: We can make every element equal to 4 by doing the following: 
- Add x to 2 once.
- Subtract x from 6 once.
- Subtract x from 8 twice.
A total of 4 operations were used.

Example 2:

Input: grid = [[1,5],[2,3]], x = 1
Output: 5
Explanation: We can make every element equal to 3.

Example 3:

Input: grid = [[1,2],[3,4]], x = 2
Output: -1
Explanation: It is impossible to make every element equal.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • 1 <= x, grid[i][j] <= 104

Solution: Median

To achieve minimum operations, the uni-value must be the median of the array.

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

C++

花花酱 LeetCode 2028. Find Missing Observations

You have observations of n + m 6-sided dice rolls with each face numbered from 1 to 6n of the observations went missing, and you only have the observations of m rolls. Fortunately, you have also calculated the average value of the n + m rolls.

You are given an integer array rolls of length m where rolls[i] is the value of the ith observation. You are also given the two integers mean and n.

Return an array of length n containing the missing observations such that the average value of the n + m rolls is exactly mean. If there are multiple valid answers, return any of them. If no such array exists, return an empty array.

The average value of a set of k numbers is the sum of the numbers divided by k.

Note that mean is an integer, so the sum of the n + m rolls should be divisible by n + m.

Example 1:

Input: rolls = [3,2,4,3], mean = 4, n = 2
Output: [6,6]
Explanation: The mean of all n + m rolls is (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.

Example 2:

Input: rolls = [1,5,6], mean = 3, n = 4
Output: [2,3,2,2]
Explanation: The mean of all n + m rolls is (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3.

Example 3:

Input: rolls = [1,2,3,4], mean = 6, n = 4
Output: []
Explanation: It is impossible for the mean to be 6 no matter what the 4 missing rolls are.

Example 4:

Input: rolls = [1], mean = 3, n = 1
Output: [5]
Explanation: The mean of all n + m rolls is (1 + 5) / 2 = 3.

Constraints:

  • m == rolls.length
  • 1 <= n, m <= 105
  • 1 <= rolls[i], mean <= 6

Solution: Math & Greedy

Total sum = (m + n) * mean
Left = Total sum – sum(rolls) = (m + n) * mean – sum(rolls)
If left > 6 * n or left < 1 * n, then there is no solution.
Otherwise, we need to distribute Left into n rolls.
There are very ways to do that, one of them is even distribution, e.g. using the average number as much as possible, and use avg + 1 to fill the gap.
Compute the average and reminder: x = left / n, r = left % n.
there will be n – r of x and r of x + 1 in the output array.

e.g. [1, 5, 6], mean = 3, n = 4
Total sum = (3 + 4) * 3 = 21
Left = 21 – (1 + 5 + 6) = 9
x = 9 / 4 = 2, r = 9 % 4 = 1
Ans = [2, 2, 2, 2+1] = [2,2,2,3]

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

C++

花花酱 LeetCode 1904. The Number of Full Rounds You Have Played

A new online video game has been released, and in this video game, there are 15-minute rounds scheduled every quarter-hour period. This means that at HH:00HH:15HH:30 and HH:45, a new round starts, where HH represents an integer number from 00 to 23. A 24-hour clock is used, so the earliest time in the day is 00:00 and the latest is 23:59.

Given two strings startTime and finishTime in the format "HH:MM" representing the exact time you started and finished playing the game, respectively, calculate the number of full rounds that you played during your game session.

  • For example, if startTime = "05:20" and finishTime = "05:59" this means you played only one full round from 05:30 to 05:45. You did not play the full round from 05:15 to 05:30 because you started after the round began, and you did not play the full round from 05:45 to 06:00 because you stopped before the round ended.

If finishTime is earlier than startTime, this means you have played overnight (from startTime to the midnight and from midnight to finishTime).

Return the number of full rounds that you have played if you had started playing at startTime and finished at finishTime.

Example 1:

Input: startTime = "12:01", finishTime = "12:44"
Output: 1
Explanation: You played one full round from 12:15 to 12:30.
You did not play the full round from 12:00 to 12:15 because you started playing at 12:01 after it began.
You did not play the full round from 12:30 to 12:45 because you stopped playing at 12:44 before it ended.

Example 2:

Input: startTime = "20:00", finishTime = "06:00"
Output: 40
Explanation: You played 16 full rounds from 20:00 to 00:00 and 24 full rounds from 00:00 to 06:00.
16 + 24 = 40.

Example 3:

Input: startTime = "00:00", finishTime = "23:59"
Output: 95
Explanation: You played 4 full rounds each hour except for the last hour where you played 3 full rounds.

Constraints:

  • startTime and finishTime are in the format HH:MM.
  • 00 <= HH <= 23
  • 00 <= MM <= 59
  • startTime and finishTime are not equal.

Solution: String / Simple math

ans = max(0, floor(end / 15) – ceil(start / 15))

Tips:

  1. Write a reusable function to parse time to minutes.
  2. a / b for floor, (a + b – 1) / b for ceil

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

C++

花花酱 LeetCode 1903. Largest Odd Number in String

You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists.

substring is a contiguous sequence of characters within a string.

Example 1:

Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Example 2:

Input: num = "4206"
Output: ""
Explanation: There are no odd numbers in "4206".

Example 3:

Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.

Constraints:

  • 1 <= num.length <= 105
  • num only consists of digits and does not contain any leading zeros.

Solution: Find right most odd digit

We just need to find the right most digit that is odd, answer will be num[0:r].

Answer must start with num[0].
Proof:
Assume the largest number is num[i:r] i > 0, we can always extend to the left, e.g. num[i-1:r] which is also an odd number and it’s larger than num[i:r] which contradicts our assumption. Thus the largest odd number (if exists) must start with num[0].

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

C++

花花酱 LeetCode 1899. Merge Triplets to Form Target Triplet

triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [ai, bi, ci] describes the ith triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain.

To obtain target, you may apply the following operation on triplets any number of times (possibly zero):

  • Choose two indices (0-indexedi and j (i != j) and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].
    • For example, if triplets[i] = [2, 5, 3] and triplets[j] = [1, 7, 5]triplets[j] will be updated to [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5].

Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.

Example 1:

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and last triplets [[2,5,3],[1,8,4],[1,7,5]]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]]
The target triplet [2,7,5] is now an element of triplets.

Example 2:

Input: triplets = [[1,3,4],[2,5,8]], target = [2,5,8]
Output: true
Explanation: The target triplet [2,5,8] is already an element of triplets.

Example 3:

Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and third triplets [[2,5,3],[2,3,4],[1,2,5],[5,2,3]]. Update the third triplet to be [max(2,1), max(5,2), max(3,5)] = [2,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]].
- Choose the third and fourth triplets [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. Update the fourth triplet to be [max(2,5), max(5,2), max(5,3)] = [5,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]].
The target triplet [5,5,5] is now an element of triplets.

Example 4:

Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Explanation: It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.

Constraints:

  • 1 <= triplets.length <= 105
  • triplets[i].length == target.length == 3
  • 1 <= ai, bi, ci, x, y, z <= 1000

Solution: Greedy

Exclude those bad ones (whose values are greater than x, y, z), check the max value for each dimension or whether there is x, y, z for each dimension.

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

C++