Posts tagged as “math”

花花酱 LeetCode 1798. Maximum Number of Consecutive Values You Can Make

By zxi on March 20, 2021

You are given an integer array coins of length n which represents the n coins that you own. The value of the i^th coin is coins[i]. You can make some value x if you can choose some of your n coins such that their values sum up to x.

Return the maximum number of consecutive integer values that you can make with your coins starting from and including 0.

Note that you may have multiple coins of the same value.

Example 1:

Input: coins = [1,3]
Output: 2
Explanation: You can make the following values:
- 0: take []
- 1: take [1]
You can make 2 consecutive integer values starting from 0.

Example 2:

Input: coins = [1,1,1,4]
Output: 8
Explanation: You can make the following values:
- 0: take []
- 1: take [1]
- 2: take [1,1]
- 3: take [1,1,1]
- 4: take [4]
- 5: take [4,1]
- 6: take [4,1,1]
- 7: take [4,1,1,1]
You can make 8 consecutive integer values starting from 0.

Example 3:

Input: nums = [1,4,10,3,1]
Output: 20

Constraints:

coins.length == n
1 <= n <= 4 * 10⁴
1 <= coins[i] <= 4 * 10⁴

Solution: Greedy + Math

We want to start with smaller values, sort input array in ascending order.

First of all, the first number has to be 1 in order to generate sum of 1.
Assuming the first i numbers can generate 0 ~ k.
Then the i+1-th number x can be used if and only if x <= k + 1, such that we can have a consecutive sum of k + 1 by adding x to a sum between [0, k] and the new maximum sum we have will be k + x.

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

C++

// Author: Huahua

class Solution {

public:

int getMaximumConsecutive(vector<int>& coins) {

sort(begin(coins), end(coins));

int ans = 0;

for (int c : coins) {

if (c > ans + 1) break;

ans += c;

}

return ans + 1;

}

};

花花酱 LeetCode 1785. Minimum Elements to Add to Form a Given Sum

By zxi on March 7, 2021

You are given an integer array nums and two integers limit and goal. The array nums has an interesting property that abs(nums[i]) <= limit.

Return the minimum number of elements you need to add to make the sum of the array equal to goal. The array must maintain its property that abs(nums[i]) <= limit.

Note that abs(x) equals x if x >= 0, and -x otherwise.

Example 1:

Input: nums = [1,-1,1], limit = 3, goal = -4
Output: 2
Explanation: You can add -2 and -3, then the sum of the array will be 1 - 1 + 1 - 2 - 3 = -4.

Example 2:

Input: nums = [1,-10,9,1], limit = 100, goal = 0
Output: 1

Constraints:

1 <= nums.length <= 10⁵
1 <= limit <= 10⁶
-limit <= nums[i] <= limit
-10⁹ <= goal <= 10⁹

Solution: Math

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

Compute the diff = abs(sum(nums) – goal)
ans = （diff + limit – 1)) / limit

C++

// Author: Huahua

class Solution {

public:

int minElements(vector<int>& nums, int limit, int goal) {

int64_t diff = abs(goal -

accumulate(begin(nums), end(nums), 0LL));

return (diff + limit - 1) / limit;

}

};

花花酱 LeetCode 1780. Check if Number is a Sum of Powers of Three

By zxi on March 6, 2021

Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.

An integer y is a power of three if there exists an integer x such that y == 3^x.

Example 1:

Input: n = 12
Output: true
Explanation: 12 = 3¹ + 3²

Example 2:

Input: n = 91
Output: true
Explanation: 91 = 3⁰ + 3² + 3⁴

Example 3:

Input: n = 21
Output: false

Constraints:

1 <= n <= 10⁷

Solution: Greedy + Math

Find the largest 3^x that <= n, subtract that from n and repeat the process.
x should be monotonically decreasing, otherwise we have duplicate terms.
e.g. 12 = 3² + 3¹ true
e.g. 21 = 3² + 3²+ 3¹ false

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

C++

// Author: Huahua

class Solution {

public:

bool checkPowersOfThree(int n) {

int last = INT_MAX;

while (n) {

int p = 0;

int cur = 1;

while (cur * 3 <= n) {

cur *= 3;

++p;

}

if (p == last) return false;

last = p;

n -= cur;

}

return true;

}

};

花花酱 LeetCode 1753. Maximum Score From Removing Stones

By zxi on February 7, 2021

You are playing a solitaire game with three piles of stones of sizes a, b, and c respectively. Each turn you choose two different non-empty piles, take one stone from each, and add 1 point to your score. The game stops when there are fewer than two non-empty piles (meaning there are no more available moves).

Given three integers a, b, and c, return the maximum score you can get.

Example 1:

Input: a = 2, b = 4, c = 6
Output: 6
Explanation: The starting state is (2, 4, 6). One optimal set of moves is:
- Take from 1st and 3rd piles, state is now (1, 4, 5)
- Take from 1st and 3rd piles, state is now (0, 4, 4)
- Take from 2nd and 3rd piles, state is now (0, 3, 3)
- Take from 2nd and 3rd piles, state is now (0, 2, 2)
- Take from 2nd and 3rd piles, state is now (0, 1, 1)
- Take from 2nd and 3rd piles, state is now (0, 0, 0)
There are fewer than two non-empty piles, so the game ends. Total: 6 points.

Example 2:

Input: a = 4, b = 4, c = 6
Output: 7
Explanation: The starting state is (4, 4, 6). One optimal set of moves is:
- Take from 1st and 2nd piles, state is now (3, 3, 6)
- Take from 1st and 3rd piles, state is now (2, 3, 5)
- Take from 1st and 3rd piles, state is now (1, 3, 4)
- Take from 1st and 3rd piles, state is now (0, 3, 3)
- Take from 2nd and 3rd piles, state is now (0, 2, 2)
- Take from 2nd and 3rd piles, state is now (0, 1, 1)
- Take from 2nd and 3rd piles, state is now (0, 0, 0)
There are fewer than two non-empty piles, so the game ends. Total: 7 points.

Example 3:

Input: a = 1, b = 8, c = 8
Output: 8
Explanation: One optimal set of moves is to take from the 2nd and 3rd piles for 8 turns until they are empty.
After that, there are fewer than two non-empty piles, so the game ends.

Constraints:

1 <= a, b, c <= 10⁵

Solution 1: Greedy

Take two stones (one each) from the largest two piles, until one is empty.

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

C++

class Solution {

public:

int maximumScore(int a, int b, int c) {

array<int, 3> s{a,b,c};

sort(begin(s), end(s));

int ans = 0;

while (s[1]-- && s[2]--) {

++ans;

sort(begin(s), end(s));

}

return ans;

}

};

Solution 2: Math

First, let’s assuming a <= b <= c.
There are two conditions:
1. a + b <= c, we can pair c with a first and then b. Total pairs is (a + b + (a + b)) / 2
2. a + b > c, we can pair c with a, b “evenly”, and then pair a with b, total pairs is (a + b + c) / 2

ans = (a + b + min(a + b, c)) / 2

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

C++

class Solution {

public:

int maximumScore(int a, int b, int c) {

array<int, 3> s{a,b,c};

sort(begin(s), end(s));

return (s[0] + s[1] + min(s[0] + s[1], s[2])) / 2;

}

};

花花酱 LeetCode 1744. Can You Eat Your Favorite Candy on Your Favorite Day?

By zxi on January 31, 2021

You are given a (0-indexed) array of positive integers candiesCount where candiesCount[i] represents the number of candies of the i^th type you have. You are also given a 2D array queries where queries[i] = [favoriteType_i, favoriteDay_i, dailyCap_i].

You play a game with the following rules:

You start eating candies on day 0.
You cannot eat any candy of type i unless you have eaten all candies of type i - 1.
You must eat at least one candy per day until you have eaten all the candies.

Construct a boolean array answer such that answer.length == queries.length and answer[i] is true if you can eat a candy of type favoriteType_i on day favoriteDay_i without eating more than dailyCap_i candies on any day, and false otherwise. Note that you can eat different types of candy on the same day, provided that you follow rule 2.

Return the constructed array answer.

Example 1:

Input: candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
Output: [true,false,true]
Explanation:
1- If you eat 2 candies (type 0) on day 0 and 2 candies (type 0) on day 1, you will eat a candy of type 0 on day 2.
2- You can eat at most 4 candies each day.
   If you eat 4 candies every day, you will eat 4 candies (type 0) on day 0 and 4 candies (type 0 and type 1) on day 1.
   On day 2, you can only eat 4 candies (type 1 and type 2), so you cannot eat a candy of type 4 on day 2.
3- If you eat 1 candy each day, you will eat a candy of type 2 on day 13.

Example 2:

Input: candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
Output: [false,true,true,false,false]

Constraints:

1 <= candiesCount.length <= 10⁵
1 <= candiesCount[i] <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 3
0 <= favoriteType_i < candiesCount.length
0 <= favoriteDay_i <= 10⁹
1 <= dailyCap_i <= 10⁹

Solution: Prefix Sum

We must have enough capacity to eat all candies before the current type.
We must have at least prefix sum candies than days, since we have to eat at least one each day.

sum[i] = sum(candyCount[0~i])
ans = {days * cap > sum[type – 1] && days <= sum[type])

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

C++

// Author: Huhua

class Solution {

public:

vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {

const int n = candiesCount.size();

vector<long> sums(n + 1);

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

sums[i] += sums[i - 1] + candiesCount[i - 1];

vector<bool> ans;

for (const auto& q : queries) {

const long type = q[0], days = q[1] + 1, cap = q[2];

ans.push_back(days * cap > sums[type] && days <= sums[type + 1]);

}

return ans;

}

};