Posts published in “Math”

花花酱 LeetCode 1819. Number of Different Subsequences GCDs

By zxi on April 6, 2021

You are given an array nums that consists of positive integers.

The GCD of a sequence of numbers is defined as the greatest integer that divides all the numbers in the sequence evenly.

For example, the GCD of the sequence [4,6,16] is 2.

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

Return the number of different GCDs among all non-empty subsequences of nums.

Example 1:

Input: nums = [6,10,3]
Output: 5
Explanation: The figure shows all the non-empty subsequences and their GCDs.
The different GCDs are 6, 10, 3, 2, and 1.

Example 2:

Input: nums = [5,15,40,5,6]
Output: 7

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 2 * 10⁵

Solution: Math

Enumerate all possible gcds (1 to max(nums)), and check whether there is a subset of the numbers that can form a given gcd i.
If we want to check whether 10 is a valid gcd, we found all multipliers of 10 in the array and compute their gcd.
ex1 gcd(10, 20, 30) = 10, true
ex2 gcd(20, 40, 80) = 20, false

Time complexity: O(mlogm)
Space complexity: O(m)

C++

// Author: Huahua

class Solution {

public:

int countDifferentSubsequenceGCDs(vector<int>& nums) {

const int kMax = *max_element(begin(nums), end(nums));

vector<int> s(kMax + 1);

for (int x : nums) s[x] = 1;

int ans = 0;

for (int i = 1; i <= kMax; ++i) {

int g = 0;

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

if (s[j]) g = gcd(g, j);

ans += g == i;

}

return ans;

}

};

花花酱 LeetCode 1808. Maximize Number of Nice Divisors

By zxi on March 27, 2021

You are given a positive integer primeFactors. You are asked to construct a positive integer n that satisfies the following conditions:

The number of prime factors of n (not necessarily distinct) is at most primeFactors.
The number of nice divisors of n is maximized. Note that a divisor of n is nice if it is divisible by every prime factor of n. For example, if n = 12, then its prime factors are [2,2,3], then 6 and 12 are nice divisors, while 3 and 4 are not.

Return the number of nice divisors of n. Since that number can be too large, return it modulo 10⁹ + 7.

Note that a prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. The prime factors of a number n is a list of prime numbers such that their product equals n.

Example 1:

Input: primeFactors = 5
Output: 6
Explanation: 200 is a valid value of n.
It has 5 prime factors: [2,2,2,5,5], and it has 6 nice divisors: [10,20,40,50,100,200].
There is not other value of n that has at most 5 prime factors and more nice divisors.

Example 2:

Input: primeFactors = 8
Output: 18

Constraints:

1 <= primeFactors <= 10⁹

Solution: Math

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

C++

// Author: Huahua

class Solution {

public:

int maxNiceDivisors(int n) {

constexpr int kMod = 1e9 + 7;

auto powm = [](long base, int exp) {

long ans = 1;

while (exp) {

if (exp & 1) ans = (ans * base) % kMod;

base = (base * base) % kMod;

exp >>= 1;

}

return ans;

};

if (n <= 3) return n;

switch (n % 3) {

case 0: return powm(3, n / 3);

case 1: return (powm(3, n / 3 - 1) * 4) % kMod;

case 2: return (powm(3, n / 3) * 2) % kMod;

}

return -1;

}

};

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

By zxi on March 6, 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 1744. Can You Eat Your Favorite Candy on Your Favorite Day?

By zxi on January 30, 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;

}

};