Posts tagged as “math”

花花酱 1276. Number of Burgers with No Waste of Ingredients

By zxi on December 2, 2019

Given two integers tomatoSlices and cheeseSlices. The ingredients of different burgers are as follows:

Jumbo Burger: 4 tomato slices and 1 cheese slice.
Small Burger: 2 Tomato slices and 1 cheese slice.

Return [total_jumbo, total_small] so that the number of remaining tomatoSlices equal to 0 and the number of remaining cheeseSlices equal to 0. If it is not possible to make the remaining tomatoSlices and cheeseSlices equal to 0 return [].

Example 1:

Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]
Explantion: To make one jumbo burger and 6 small burgers we need 4*1 + 2*6 = 16 tomato and 1 + 6 = 7 cheese. There will be no remaining ingredients.

Example 2:

Input: tomatoSlices = 17, cheeseSlices = 4
Output: []
Explantion: There will be no way to use all ingredients to make small and jumbo burgers.

Example 3:

Input: tomatoSlices = 4, cheeseSlices = 17
Output: []
Explantion: Making 1 jumbo burger there will be 16 cheese remaining and making 2 small burgers there will be 15 cheese remaining.

Example 4:

Input: tomatoSlices = 0, cheeseSlices = 0
Output: [0,0]

Example 5:

Input: tomatoSlices = 2, cheeseSlices = 1
Output: [0,1]

Constraints:

0 <= tomatoSlices <= 10^7
0 <= cheeseSlices <= 10^7

Solution: Math

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

C++

// Author: Huahua

class Solution {

public:

vector<int> numOfBurgers(int T, int C) {

// Jumbo = x, small = y

// 4x + 2y = T

// x + y = C

// x = (T - 2C) / 2

int x = T / 2 - C;

int y = C - x;

if (4 * x + 2 * y == T && x >= 0 && y >= 0) return {x, y};

return {};

}

};

花花酱 LeetCode 1266. Minimum Time Visiting All Points

By zxi on November 24, 2019

On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
You have to visit the points in the same order as they appear in the array.

Example 1:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
Time from [1,1] to [3,4] = 3 seconds 
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds

Example 2:

Input: points = [[3,2],[-2,2]]
Output: 5

Constraints:

points.length == n
1 <= n <= 100
points[i].length == 2
-1000 <= points[i][0], points[i][1] <= 1000

Solution: Geometry + Greedy

dx = abs(x1 – x2)
dy = abs(y1 – y2)

go diagonally first for min(dx, dy) steps, and then go straight line for abs(dx – dy) steps.

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

C++

// Author: Huahua

class Solution {

public:

int minTimeToVisitAllPoints(vector<vector<int>>& points) {

int ans = 0;

for (size_t i = 1; i < points.size(); ++i) {

int dx = abs(points[i - 1][0] - points[i][0]);

int dy = abs(points[i - 1][1] - points[i][1]);

ans += min(dx, dy) + abs(dx - dy);

}

return ans;

}

};

花花酱 LeetCode 1250. Check If It Is a Good Array

By zxi on November 8, 2019

Given an array nums of positive integers. Your task is to select some subset of nums, multiply each element by an integer and add all these numbers. The array is said to be good if you can obtain a sum of 1 from the array by any possible subset and multiplicand.

Return True if the array is good otherwise return False.

Example 1:

Input: nums = [12,5,7,23]
Output: true
Explanation: Pick numbers 5 and 7.
5*3 + 7*(-2) = 1

Example 2:

Input: nums = [29,6,10]
Output: true
Explanation: Pick numbers 29, 6 and 10.
29*1 + 6*(-3) + 10*(-1) = 1

Example 3:

Input: nums = [3,6]
Output: false

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

Solution: Math

Bézout’s lemma: b[1] * A[1] + b[2] * A[2] + …. + b[n] * A[n] = 1 <==> gcd(A[1], A[2], …, A[n]) = 1 <=> at least two numbers are co-prime

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

C++

// Author: Huahua

class Solution {

public:

bool isGoodArray(vector<int>& nums) {

int g = nums[0];

for (int x : nums)

g = gcd(g, x);

return g == 1;

}

};

花花酱 LeetCode 1247. Minimum Swaps to Make Strings Equal

By zxi on November 7, 2019

You are given two strings s1 and s2 of equal length consisting of letters "x" and "y" only. Your task is to make these two strings equal to each other. You can swap any two characters that belong to different strings, which means: swap s1[i] and s2[j].

Return the minimum number of swaps required to make s1 and s2 equal, or return -1 if it is impossible to do so.

Example 1:

Input: s1 = "xx", s2 = "yy"
Output: 1
Explanation: 
Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".

Example 2:

Input: s1 = "xy", s2 = "yx"
Output: 2
Explanation: 
Swap s1[0] and s2[0], s1 = "yy", s2 = "xx".
Swap s1[0] and s2[1], s1 = "xy", s2 = "xy".
Note that you can't swap s1[0] and s1[1] to make s1 equal to "yx", cause we can only swap chars in different strings.

Example 3:

Input: s1 = "xx", s2 = "xy"
Output: -1

Example 4:

Input: s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
Output: 4

Constraints:

1 <= s1.length, s2.length <= 1000
s1, s2 only contain 'x' or 'y'.

Solution: Math

if s1[i] == s2[i] than no need to swap, so we can only look for
case1. s1[i] = x, s2[i] = y, xy
case2. s1[i] = y, s2[i] = x, yx

If case1 + case2 is odd, then there’s no solution.

Otherwise we can use one swap to fix two xys (or two yxs)
xx, yy => xy, yx

One special case is there an extra xy and and extra yx, which takes two swaps
xy, yx => yy, xx => xy, xy

Finally,
ans = (case1 + 1) / 2 + (case2 + 1) / 2

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

C++

// Author: Huahua

class Solution {

public:

int minimumSwap(string s1, string s2) {

int xy = 0;

int yx = 0;

for (int i = 0; i < s1.length(); ++i) {

if (s1[i] == 'x' && s2[i] == 'y') ++xy;

if (s1[i] == 'y' && s2[i] == 'x') ++yx;

}

if ((xy + yx) % 2) return -1;

return (xy + 1) / 2 + (yx + 1) / 2;

}

};

花花酱 LeetCode 1217. Play with Chips

By zxi on October 6, 2019

There are some chips, and the i-th chip is at position chips[i].

You can perform any of the two following types of moves any number of times (possibly zero) on any chip:

Move the i-th chip by 2 units to the left or to the right with a cost of 0.
Move the i-th chip by 1 unit to the left or to the right with a cost of 1.

There can be two or more chips at the same position initially.

Return the minimum cost needed to move all the chips to the same position (any position).

Example 1:

Input: chips = [1,2,3]
Output: 1
Explanation: Second chip will be moved to positon 3 with cost 1. First chip will be moved to position 3 with cost 0. Total cost is 1.

Example 2:

Input: chips = [2,2,2,3,3]
Output: 2
Explanation: Both fourth and fifth chip will be moved to position two with cost 1. Total minimum cost will be 2.

Constraints:

1 <= chips.length <= 100
1 <= chips[i] <= 10^9

Solution: Math

We can choose either:
1. move all odd positions to an arbitrary even position and move the rest to the same position
2. move all even positions to an arbitrary odd position and move the rest to the same position
ans = min(# of odd pos, # of even pos)

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

C++

// Author: Huahua

class Solution {

public:

int minCostToMoveChips(vector<int>& chips) {

int odd = 0;

int even = 0;

for (int p : chips) {

if (p % 2) {

++odd;

} else {

++even;

}

return min(odd, even);

}

};