Posts published in “Algorithms”

花花酱 LeetCode 2231. Largest Number After Digit Swaps by Parity

By zxi on April 9, 2022

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.

Example 1:

Input: num = 1234
Output: 3412
Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.
Swap the digit 2 with the digit 4, this results in the number 3412.
Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.
Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.

Example 2:

Input: num = 65875
Output: 87655
Explanation: Swap the digit 8 with the digit 6, this results in the number 85675.
Swap the first digit 5 with the digit 7, this results in the number 87655.
Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.

Constraints:

1 <= num <= 10⁹

Solution:

Put all even digits into one array, all odd digits into another one, all digits into the third. Sort two arrays, and generate a new number from sorted arrays.

Time complexity: O(logn*loglogn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

int largestInteger(int num) {

vector<int> odd, even, org;

for (int cur = num; cur; cur /= 10) {

((cur & 1) ? odd : even).push_back(cur % 10);

org.push_back(cur % 10);

}

sort(begin(odd), end(odd));

sort(begin(even), end(even));

int ans = 0;

for (int i = 0; i < org.size(); ++i) {

if (i) ans *= 10;

auto& cur = (org[org.size() - i - 1] & 1) ? odd : even;

ans += cur.back();

cur.pop_back();

}

return ans;

}

};

花花酱 LeetCode 2226. Maximum Candies Allocated to K Children

By zxi on April 2, 2022

You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can take at most one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

Example 1:

Input: candies = [5,8,6], k = 3
Output: 5
Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.

Example 2:

Input: candies = [2,5], k = 11
Output: 0
Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.

Constraints:

1 <= candies.length <= 10⁵
1 <= candies[i] <= 10⁷
1 <= k <= 10¹²

Solution: Binary Search

Find the smallest L s.t. we can allocate candies to less than k children.

ans = L – 1.

Time complexity: O(nlogm) where n is number of piles, m is sum(candies) / k.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maximumCandies(vector<int>& candies, long long k) {

long long total = accumulate(begin(candies), end(candies), 0LL);

long long l = 1;

long long r = total / k + 1;

while (l < r) {

long long m = l + (r - l) / 2;

long long c = 0;

for (int pile : candies)

c += pile / m;

if (c < k)

r = m;

else

l = m + 1;

}

return l - 1;

}

};

花花酱 LeetCode 2176. Count Equal and Divisible Pairs in an Array

By zxi on March 4, 2022

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs(i, j)where0 <= i < j < n, such thatnums[i] == nums[j]and(i * j)is divisible byk.

Example 1:

Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation:
There are 4 pairs that meet all the requirements:
- nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
- nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
- nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
- nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.

Constraints:

1 <= nums.length <= 100
1 <= nums[i], k <= 100

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countPairs(vector<int>& nums, int k) {

const int n = nums.size();

int ans = 0;

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

for (int j = i + 1; j < n; ++j)

ans += (nums[i] == nums[j]) && (i * j % k == 0);

return ans;

}

};

花花酱 LeetCode 2187. Minimum Time to Complete Trips

By zxi on February 27, 2022

You are given an array time where time[i] denotes the time taken by the i^th bus to complete one trip.

Each bus can make multiple trips successively; that is, the next trip can start immediately after completing the current trip. Also, each bus operates independently; that is, the trips of one bus do not influence the trips of any other bus.

You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete at least totalTrips trips.

Example 1:

Input: time = [1,2,3], totalTrips = 5
Output: 3
Explanation:
- At time t = 1, the number of trips completed by each bus are [1,0,0]. 
  The total number of trips completed is 1 + 0 + 0 = 1.
- At time t = 2, the number of trips completed by each bus are [2,1,0]. 
  The total number of trips completed is 2 + 1 + 0 = 3.
- At time t = 3, the number of trips completed by each bus are [3,1,1]. 
  The total number of trips completed is 3 + 1 + 1 = 5.
So the minimum time needed for all buses to complete at least 5 trips is 3.

Example 2:

Input: time = [2], totalTrips = 1
Output: 2
Explanation:
There is only one bus, and it will complete its first trip at t = 2.
So the minimum time needed to complete 1 trip is 2.

Constraints:

1 <= time.length <= 10⁵
1 <= time[i], totalTrips <= 10⁷

Solution: Binary Search

Find the smallest t s.t. trips >= totalTrips.

Time complexity: O(nlogm), where m ~= 1e15
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

long long minimumTime(vector<int>& time, int totalTrips) {

long long l = 1;

long long r = 1e15;

while (l < r) {

long long m = l + (r - l) / 2;

long long trips = 0;

for (int t : time) {

trips += m / t;

if (trips >= totalTrips) break;

}

if (trips >= totalTrips)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 2155. All Divisions With the Highest Score of a Binary Array

By zxi on February 4, 2022

You are given a 0-indexed binary array nums of length n. nums can be divided at index i (where 0 <= i <= n) into two arrays (possibly empty) nums_left and nums_right:

nums_left has all the elements of nums between index 0 and i - 1 (inclusive), while nums_right has all the elements of nums between index i and n - 1 (inclusive).
If i == 0, nums_left is empty, while nums_right has all the elements of nums.
If i == n, nums_left has all the elements of nums, while nums_right is empty.

The division score of an index i is the sum of the number of 0‘s in nums_left and the number of 1‘s in nums_right.

Return all distinct indices that have the highest possible division score. You may return the answer in any order.

Example 1:

Input: nums = [0,0,1,0]
Output: [2,4]
Explanation: Division at index
- 0: nums_left is []. nums_right is [0,0,1,0]. The score is 0 + 1 = 1.
- 1: nums_left is [0]. nums_right is [0,1,0]. The score is 1 + 1 = 2.
- 2: nums_left is [0,0]. nums_right is [1,0]. The score is 2 + 1 = 3.
- 3: nums_left is [0,0,1]. nums_right is [0]. The score is 2 + 0 = 2.
- 4: nums_left is [0,0,1,0]. nums_right is []. The score is 3 + 0 = 3.
Indices 2 and 4 both have the highest possible division score 3.
Note the answer [4,2] would also be accepted.

Example 2:

Input: nums = [0,0,0]
Output: [3]
Explanation: Division at index
- 0: nums_left is []. nums_right is [0,0,0]. The score is 0 + 0 = 0.
- 1: nums_left is [0]. nums_right is [0,0]. The score is 1 + 0 = 1.
- 2: nums_left is [0,0]. nums_right is [0]. The score is 2 + 0 = 2.
- 3: nums_left is [0,0,0]. nums_right is []. The score is 3 + 0 = 3.
Only index 3 has the highest possible division score 3.

Example 3:

Input: nums = [1,1]
Output: [0]
Explanation: Division at index
- 0: nums_left is []. nums_right is [1,1]. The score is 0 + 2 = 2.
- 1: nums_left is [1]. nums_right is [1]. The score is 0 + 1 = 1.
- 2: nums_left is [1,1]. nums_right is []. The score is 0 + 0 = 0.
Only index 0 has the highest possible division score 2.

Constraints:

n == nums.length
1 <= n <= 10⁵
nums[i] is either 0 or 1.

Solution: Precompute + Prefix Sum

Count how many ones in the array, track the prefix sum to compute score for each index in O(1).

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

C++

// Author: Huahua

class Solution {

public:

vector<int> maxScoreIndices(vector<int>& nums) {

const int n = nums.size();

const int t = accumulate(begin(nums), end(nums), 0);

vector<int> ans;

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

const int s = (i - p) + (t - p);

if (s > b) {

b = s; ans.clear();

}

if (s == b) ans.push_back(i);

if (i != n) p += nums[i];

}

return ans;

}

};