Huahua’s Tech Road

花花酱 LeetCode 1552. Magnetic Force Between Two Balls

By zxi on August 15, 2020

In universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the i^th basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.

Rick stated that magnetic force between two different balls at positions x and y is |x - y|.

Given the integer array position and the integer m. Return the required force.

Example 1:

Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.

Example 2:

Input: position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999
Explanation: We can use baskets 1 and 1000000000.

Constraints:

n == position.length
2 <= n <= 10^5
1 <= position[i] <= 10^9
All integers in position are distinct.
2 <= m <= position.length

Solution: Binary Search

Find the max distance that we can put m balls.

Time complexity: O(n*log(distance))
Space complexity: O(1)

C++

class Solution {

public:

int maxDistance(vector<int>& position, int m) {

const int n = position.size();

sort(begin(position), end(position));

auto count = [&](int d) -> int {

int last = position[0];

int ans = 1;

for (int x : position) {

if (x - last >= d) {

last = x;

++ans;

}

return ans;

};

int l = 0;

int t = (position.back() - position.front()) + 1;

int r = t;

while (l < r) {

int mid = l + (r - l) / 2;

if (count(t - mid) >= m) // find min of l => max of t - l

r = mid;

else

l = mid + 1;

}

return t - l;

}

};

Java

class Solution {

public int maxDistance(int[] position, int m) {

Arrays.sort(position);

final int n = position.length;

int l = 0;

int r = position[n - 1] - position[0] + 1;

int t = r;

while (l < r) {

int mid = l + (r - l) / 2;

if (getCount(position, t - mid) >= m)

r = mid;

else

l = mid + 1;

}

return t - l;

}

private int getCount(int[] position, int d) {

int count = 1;

int last = position[0];

for (int x : position) {

if (x - last >= d) {

++count;

last = x;

}

return count;

}

Python3

class Solution:

def maxDistance(self, position: List[int], m: int) -> int:

position.sort()

def getCount(d: int) -> int:

last, count = position[0], 1

for x in position:

if x - last >= d:

last = x

count += 1

return count

l, r = 0, position[-1] - position[0] + 1

t = r

while l < r:

mid = l + (r - l) // 2

if getCount(t - mid) >= m:

r = mid

else:

l = mid + 1

return t - l

花花酱 LeetCode 1551. Minimum Operations to Make Array Equal

By zxi on August 15, 2020

You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e. 0 <= i < n).

In one operation, you can select two indices x and y where 0 <= x, y < n and subtract 1 from arr[x] and add 1 to arr[y] (i.e. perform arr[x] -=1 and arr[y] += 1). The goal is to make all the elements of the array equal. It is guaranteed that all the elements of the array can be made equal using some operations.

Given an integer n, the length of the array. Return the minimum number of operations needed to make all the elements of arr equal.

Example 1:

Input: n = 3
Output: 2
Explanation: arr = [1, 3, 5]
First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4]
In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].

Example 2:

Input: n = 6
Output: 9

Constraints:

1 <= n <= 10^4

Solution: Math

1: Find the mean (final value) of the array, assuming x, easy to show x == n
2: Compute the sum of an arithmetic progression of (x – 1) + (x – 3) + … for n // 2 pairs

e.g. n = 6
arr = [1, 3, 5, 7, 9, 11]
x = (1 + 2 * n – 1) / 2 = 6 = n
steps = (6 – 1) + (6 – 3) + (6 – 5) = (n // 2) * (n – (1 + n – 1) / 2) = (n // 2) * (n – n // 2) = 3 * 3 = 9

e.g. n = 5
arr = [1,3,5,7,9]
x = (1 + 2 * n – 1) / 2 = 5 = n
steps = (5 – 1) + (5 – 3)= (n//2) * (n – n // 2) = (n // 2) * ((n + 1) // 2) = 2 * 3 = 6

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

C++

class Solution {

public:

int minOperations(int n) {

return (n / 2) * ((n + 1) / 2);

}

};

花花酱 LeetCode 1550. Three Consecutive Odds

By zxi on August 15, 2020

Given an integer array arr, return true if there are three consecutive odd numbers in the array. Otherwise, return false.

Example 1:

Input: arr = [2,6,4,1]
Output: false
Explanation: There are no three consecutive odds.

Example 2:

Input: arr = [1,2,34,3,4,5,7,23,12]
Output: true
Explanation: [5,7,23] are three consecutive odds.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000

Solution: Counting

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

C++

class Solution {

public:

bool threeConsecutiveOdds(vector<int>& arr) {

int count = 0;

for (int x : arr) {

if (x & 1) {

if (++count == 3) return true;

} else {

count = 0;

}

return false;

}

};

花花酱 LeetCode 1547. Minimum Cost to Cut a Stick

By zxi on August 11, 2020

Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:

Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.

You should perform the cuts in order, you can change the order of the cuts as you wish.

The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.

Return the minimum total cost of the cuts.

Example 1:

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:

The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).

Example 2:

Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering the cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.

Constraints:

2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
All the integers in cuts array are distinct.

Solution: Range DP

dp[i][j] := min cost to finish the i-th cuts to the j-th (in sorted order)
dp[i][j] = r – l + min(dp[i][k – 1], dp[k + 1][j]) # [l, r] is the current stick range.

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

C++

class Solution {

public:

int minCost(int n, vector<int>& cuts) {

const int kInf = 1e9;

sort(begin(cuts), end(cuts));

const int c = cuts.size();

vector<vector<int>> cost(c + 1, vector<int>(c + 1, kInf));

// Min cost to finish i-th cuts to the j-th cut with stick in range [l, r].

function<int(int, int, int, int)> dp = [&](int i, int j, int l, int r) {

if (i > j) return 0; // Done

if (i == j) return r - l; // One cut, the length of the stick.

if (cost[i][j] != kInf) return cost[i][j];

int& ans = cost[i][j];

for (int k = i; k <= j; ++k)

ans = min(ans, r - l

+ dp(i, k - 1, l, cuts[k])

+ dp(k + 1, j, cuts[k], r));

return ans;

};

return dp(0, c - 1, 0, n);

}

};

Java

class Solution {

public int minCost(int n, int[] cuts) {

Arrays.sort(cuts);

final int c = cuts.length;

int[][] dp = new int[c][c];

return solve(dp, cuts, 0, c - 1, 0, n);

}

private int solve(int[][] dp, int[] cuts, int i, int j, int l, int r) {

if (i > j) return 0;

if (i == j) return r - l;

if (dp[i][j] != 0) return dp[i][j];

int ans = Integer.MAX_VALUE;

for (int k = i; k <= j; ++k)

ans = Math.min(ans, r - l

+ solve(dp, cuts, i, k - 1, l, cuts[k])

+ solve(dp, cuts, k + 1, j, cuts[k], r));

return dp[i][j] = ans;

}

Python3

class Solution:

def minCost(self, n: int, cuts: List[int]) -> int:

@lru_cache(maxsize=None)

def dp(i, j, l, r):

if i > j: return 0

if i == j: return r - l

return r - l + min(dp(i, k - 1, l, cuts[k])

+ dp(k + 1, j, cuts[k], r)

for k in range(i, j + 1))

cuts.sort()

return dp(0, len(cuts) - 1, 0, n)

花花酱 LeetCode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

By zxi on August 11, 2020

Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).

Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3

Example 4:

Input: nums = [0,0,0], target = 0
Output: 3

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6

Solution: Prefix Sum + DP

Use a hashmap index to record the last index when a given prefix sum occurs.
dp[i] := max # of non-overlapping subarrays of nums[0~i], nums[i] is not required to be included.
dp[i+1] = max(dp[i], // skip nums[i]
dp[index[sum – target] + 1] + 1) // use nums[i] to form a new subarray
ans = dp[n]

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

C++

class Solution {

public:

int maxNonOverlapping(vector<int>& nums, int target) {

const int n = nums.size();

vector<int> dp(n + 1, 0); // ans at nums[i];

unordered_map<int, int> index; // {prefix sum -> last_index}

index[0] = -1;

int sum = 0;

for (int i = 0; i < n; ++i) {

sum += nums[i];

int t = sum - target;

dp[i + 1] = dp[i];

if (index.count(t))

dp[i + 1] = max(dp[i + 1], dp[index[t] + 1] + 1);

index[sum] = i;

}

return dp[n];

}

};

Huahua's Tech Road

花花酱 LeetCode 1552. Magnetic Force Between Two Balls

Solution: Binary Search

C++

Java

Python3

花花酱 LeetCode 1551. Minimum Operations to Make Array Equal

Solution: Math

C++

花花酱 LeetCode 1550. Three Consecutive Odds

Solution: Counting

C++

花花酱 LeetCode 1547. Minimum Cost to Cut a Stick

Solution: Range DP

C++

Java

Python3

花花酱 LeetCode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Solution: Prefix Sum + DP

C++