Posts tagged as “math”

花花酱 LeetCode 970. Powerful Integers

By zxi on January 5, 2019

Given two non-negative integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0.

Return a list of all powerful integers that have value less than or equal to bound.

You may return the answer in any order. In your answer, each value should occur at most once.

Example 1:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation: 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

Example 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]

Note:

1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6

Solution: Brute Force

Time complexity: O(log(bound) / log(x) * log(bound) / log(y))
Space complexity: O(log(bound) / log(x) * log(bound) / log(y))

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<int> powerfulIntegers(int x, int y, int bound) {

unordered_set<int> ans;

for (int a = 1; a < bound; a *= x) {

for (int b = 1; a + b <= bound; b *= y) {

ans.insert(a + b);

if (y == 1) break;

}

if (x == 1) break;

}

return {begin(ans), end(ans)};

}

};

花花酱 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 954. Array of Doubled Pairs

By zxi on December 9, 2018

Problem

Given an array of integers A with even length, return true if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i] for every 0 <= i < len(A) / 2.

Example 1:

Input: [3,1,3,6]
Output: false

Example 2:

Input: [2,1,2,6]
Output: false

Example 3:

Input: [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Example 4:

Input: [1,2,4,16,8,4]
Output: false

Note:

0 <= A.length <= 30000
A.length is even
-100000 <= A[i] <= 100000

Solution 1:

Time complexity: O(N + 100000 * 2)

Space complexity: O(100000 * 2)

C++

// Author: Huahua, 108 ms

class Solution {

public:

bool canReorderDoubled(vector<int>& A) {

const int kMaxN = 100000;

vector<int> p(kMaxN + 1);

vector<int> n(kMaxN + 1);

for (int a : A) {

if (a >= 0) ++p[a];

else ++n[-a];

}

for (int i = 0; i <= kMaxN / 2; ++i) {

if (p[i] && (p[i * 2] -= p[i]) < 0) return false;

if (n[i] && (n[i * 2] -= n[i]) < 0) return false;

}

return true;

}

};

Solution 2:

Time complexity: O(NlogN)

Space complexity: O(N)

C++

// Author: Huahua, 108 ms

class Solution {

public:

bool canReorderDoubled(vector<int>& A) {

unordered_map<int, int> c;

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

vector<int> keys;

for (const auto &kv : c) keys.push_back(kv.first);

sort(begin(keys), end(keys), [](int a, int b) { return abs(a) < abs(b); });

for (int key : keys)

if (c[key] && (c[key * 2] -= c[key]) < 0) return false;

return true;

}

};

花花酱 LeetCode 939. Minimum Area Rectangle

By zxi on November 11, 2018

Problem

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Example 2:

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2

Note:

1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.

Solution 1: HashTable + Brute Force

Try all pairs of points to form a diagonal and see whether pointers of another diagonal exist or not.

Assume two points are (x0, y0), (x1, y1) x0 != x1 and y0 != y1. The other two points will be (x0, y1), (x1, y0)

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua, running time: 96 ms

class Solution {

public:

int minAreaRect(vector<vector<int>>& points) {

unordered_map<int, unordered_set<int>> s;

for (const auto& point : points)

s[point[0]].insert(point[1]);

const int n = points.size();

int min_area = INT_MAX;

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

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

int x0 = points[i][0];

int y0 = points[i][1];

int x1 = points[j][0];

int y1 = points[j][1];

if (x0 == x1 || y0 == y1) continue;

int area = abs(x0 - x1) * abs(y0 - y1);

if (area > min_area) continue;

if (!s[x1].count(y0) || !s[x0].count(y1)) continue;

min_area = area;

}

return min_area == INT_MAX ? 0 : min_area;

}

};

C++ / 1D hashtable

// Author: Huahua, 68 ms

class Solution {

public:

int minAreaRect(vector<vector<int>>& points) {

unordered_set<int> s;

for (const auto& point : points)

s.insert((point[0] << 16) | point[1]);

const int n = points.size();

int min_area = INT_MAX;

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

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

int x0 = points[i][0];

int y0 = points[i][1];

int x1 = points[j][0];

int y1 = points[j][1];

if (x0 == x1 || y0 == y1) continue;

int area = abs(x0 - x1) * abs(y0 - y1);

if (area > min_area) continue;

int p0 = (x1 << 16) | y0;

int p1 = (x0 << 16) | y1;

if (!s.count(p0) || !s.count(p1)) continue;

min_area = area;

}

return min_area == INT_MAX ? 0 : min_area;

}

};

花花酱 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;

}

};