Posts published in “Math”

花花酱 LeetCode 313. Super Ugly Number

By zxi on January 2, 2019

Write a program to find the n^th super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.

Example:

Input: n = 12, primes = [2,7,13,19] 
Output: 32  
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12               super ugly numbers given primes = [2,7,13,19] of size 4.

Note:

1 is a super ugly number for any given primes.
The given numbers in primes are in ascending order.
0 < k ≤ 100, 0 < n ≤ 10⁶, 0 < primes[i] < 1000.
The n^th super ugly number is guaranteed to fit in a 32-bit signed integer.

Solution 1: Set

Maintain an ordered set of super ugly numbers, each time extract the smallest one, and multiply it with all primes and insert the new number into set.

Time complexity: O(n*k*logn)
Space complexity: O(n)

C++

// Author: Huahua, running time: 484 ms

class Solution {

public:

int nthSuperUglyNumber(int n, vector<int>& primes) {

if (n == 1) return 1;

set<int> q{begin(primes), end(primes)};

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

auto it = begin(q);

int t = *it;

q.erase(it);

for (int p : primes) {

if (INT_MAX / t < p) continue;

q.insert(p * t);

}

return *begin(q);

}

};

Solution 2: Priority Queue

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

C++

// Author: Huahua, 40 ms

struct Node {

int num;

int index;

int prime;

bool operator>(const Node& o) const {

if (this->num == o.num) return this->index > o.index;

return this->num > o.num;

}

};

class Solution {

public:

int nthSuperUglyNumber(int n, vector<int>& primes) {

if (n == 1) return 1;

vector<int> nums(n, 1);

priority_queue<Node, vector<Node>, greater<Node>> q;

for (int p : primes)

q.push({p, 1, p});

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

nums[i] = q.top().num;

while (nums[i] == q.top().num) {

Node node = std::move(q.top()); q.pop();

node.num = nums[node.index++] * node.prime;

q.push(std::move(node));

}

return nums.back();

}

};

花花酱 LeetCode 470. Implement Rand10() Using Rand7()

By zxi on October 15, 2018

Problem

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

Input: 3
Output: [8,1,10]

Note:

rand7 is predefined.
Each testcase has one argument: n, the number of times that rand10 is called.

Follow up:

What is the expected value for the number of calls to rand7() function?
Could you minimize the number of calls to rand7()?

Solution:

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int rand10() {

int index = INT_MAX;

while (index >= 40)

index = 7 * (rand7() - 1) + (rand7() - 1);

return index % 10 + 1;

}

};

花花酱 LeetCode 923. 3Sum With Multiplicity

By zxi on October 13, 2018

Problem

Given an integer array A, and an integer target, return the number of tuples i, j, k such that i < j < k and A[i] + A[j] + A[k] == target.

As the answer can be very large, return it modulo 10^9 + 7.

Example 1:

Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: 
Enumerating by the values (A[i], A[j], A[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

Example 2:

Input: A = [1,1,2,2,2,2], target = 5
Output: 12
Explanation: 
A[i] = 1, A[j] = A[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

Note:

3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300

Solution: Math / Combination

Time complexity: O(n + |target|^2)

Space complexity: O(|target|)

C++

// Author: Huahua, runtime: 4 ms

class Solution {

public:

int threeSumMulti(vector<int>& A, int target) {

constexpr int kMaxN = 100;

constexpr int kMod = 1e9 + 7;

vector<long> c(kMaxN + 1, 0);

for (int a : A) ++c[a];

long ans = 0;

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

for (int j = i; j <= target; ++j) {

const int k = target - i - j;

if (k < 0 || k >= c.size() || k < j) continue;

if (!c[i] || !c[j] || !c[k]) continue;

if (i == j && j == k)

ans += (c[i] - 2) * (c[i] - 1) * c[i] / 6;

else if (i == j && j != k)

ans += c[i] * (c[i] - 1) / 2 * c[k];

else if (i != j && j == k)

ans += c[i] * (c[j] - 1) * c[j] / 2;

else

ans += c[i] * c[j] * c[k];

}

return ans % kMod;

}

};

花花酱 LeetCode 914. X of a Kind in a Deck of Cards

By zxi on September 30, 2018

Problem

n a deck of cards, each card has an integer written on it.

Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:

Each group has exactly X cards.
All the cards in each group have the same integer.

Example 1:

Input: [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4]

Example 2:

Input: [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.

Example 3:

Input: [1]
Output: false
Explanation: No possible partition.

Example 4:

Input: [1,1]
Output: true
Explanation: Possible partition [1,1]

Example 5:

Input: [1,1,2,2,2,2]
Output: true
Explanation: Possible partition [1,1],[2,2],[2,2]

Note:

1 <= deck.length <= 10000
0 <= deck[i] < 10000

Solution 1: HashTable + Brute Force

Try all possible Xs. 2 ~ deck.size()

Time complexity: ~O(n)

Space complexity: O(1)

C++

// Author: Huahua, 16 ms

class Solution {

public:

bool hasGroupsSizeX(vector<int>& deck) {

unordered_map<int, int> counts;

for (int card : deck) ++counts[card];

for (int i = 2; i <= deck.size(); ++i) {

if (deck.size() % i) continue;

bool ok = true;

for (const auto& pair : counts)

if (pair.second % i) {

ok = false;

break;

}

if (ok) return true;

}

return false;

}

};

Solution 2: HashTable + GCD

Time complexity: O(nlogn)

Space complexity: O(1)

C++

// Author: Huahua, 16 ms

class Solution {

public:

bool hasGroupsSizeX(vector<int>& deck) {

unordered_map<int, int> counts;

for (int card : deck) ++counts[card];

int X = deck.size();

for (const auto& p : counts)

X = __gcd(X, p.second);

return X >= 2;

}

};

Java

// Author: Somebody

class Solution {

public boolean hasGroupsSizeX(int[] deck) {

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

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

int curr = deck[i];

if (map.containsKey(curr)) {

map.put(curr, map.get(curr) + 1);

} else {

map.put(curr, 1);

}

// O(nLogn)

int gcd = 0;

for(Integer key: map.keySet()) {

gcd = findGCDOfTwoNumbers(map.get(key), gcd);

}

return gcd >= 2;

}

// O(Log n)

public static int findGCDOfTwoNumbers (int a, int b) {

if (b == 0) {

return a;

}

return findGCDOfTwoNumbers(b, a%b);

}

花花酱 LeetCode 908. Smallest Range I

By zxi on September 23, 2018

Problem

Given an array A of integers, for each integer A[i] we may choose any x with -K <= x <= K, and add xto A[i].

After this process, we have some array B.

Return the smallest possible difference between the maximum value of B and the minimum value of B.

Example 1:

Input: A = [1], K = 0
Output: 0
Explanation: B = [1]

Example 2:

Input: A = [0,10], K = 2
Output: 6
Explanation: B = [2,8]

Example 3:

Input: A = [1,3,6], K = 3
Output: 0
Explanation: B = [3,3,3] or B = [4,4,4]

Note:

1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000

Solution 0: Brute Force (TLE)

Try all pairs

Time complexity: O(n^2)

Space complexity: O(1)

Solution 1: Math

Time complexity: O(n)

Space complexity: O(1)

Find the min/max element of the array.

min + k v.s. max – k

ans = max(0, (max – min) – 2 * k))

C++

// Author: Huahua

class Solution {

public:

int smallestRangeI(vector<int>& A, int K) {

int a_min = *min_element(begin(A), end(A));

int a_max = *max_element(begin(A), end(A));

return max(0, (a_max - a_min) - 2 * K);

}

};

Python3

# Author: Huahua, 72 ms

class Solution:

def smallestRangeI(self, A, K):

return max(0, max(A) - min(A) - 2 * K);