Posts published in “Math”

花花酱 LeetCode 66. Plus One

By zxi on April 10, 2019

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution: Big Integer

Process from right to left (lest significant to most signification). Use carry to indicate whether need +1 for next digit or not.

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

c++

class Solution {

public:

vector<int> plusOne(vector<int>& digits) {

int carry = 1;

for (int i = digits.size() - 1; i >= 0; --i) {

digits[i] += carry;

carry = digits[i] / 10;

digits[i] %= 10;

}

if (carry) digits.insert(begin(digits), carry);

return digits;

}

};

花花酱 LeetCode 781. Rabbits in Forest

By zxi on February 9, 2019

In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.

Examples:
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit than answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

Input: answers = [10, 10, 10]
Output: 11

Input: answers = []
Output: 0

Note:

answers will have length at most 1000.
Each answers[i] will be an integer in the range [0, 999].

Solution: Math

Say there n rabbits answered x.
if n <= x: they can have the same color
if n > x: they must be divided into groups, each group has x + 1 rabbits, and there are at least ceil(n / (x+1)) groups.
So there will be ceil(n / (x + 1)) * (x + 1) rabbits. This expression can be expressed as (n + x) / (x + 1) * (x + 1) in programming languages. (n + x) // (x + 1) * (x + 1) for Python3.

C++

// Author: Huahua, running time: 8 ms / 5.2 MB

class Solution {

public:

int numRabbits(vector<int>& answers) {

vector<int> counts(*max_element(begin(answers), end(answers)) + 1);

for (const int answer : answers)

++counts[answer];

int total = 0;

for (int x = 0; x < counts.size(); ++x)

total += (counts[x] + x) / (x + 1) * (x + 1);

return total;

}

};

Python3

# Author: Huahua, running time: 36 ms / 6.5 MB

class Solution:

def numRabbits(self, answers: 'List[int]') -> 'int':

counts = collections.Counter(answers)

return sum([(n + x) // (x + 1) * (x + 1) for x, n in counts.items()])

花花酱 LeetCode 972. Equal Rational Numbers

By zxi on January 5, 2019

Given two strings S and T, each of which represents a non-negative rational number, return True if and only if they represent the same number. The strings may use parentheses to denote the repeating part of the rational number.

In general a rational number can be represented using up to three parts: an integer part, a non-repeating part, and a repeating part. The number will be represented in one of the following three ways:

<IntegerPart> (e.g. 0, 12, 123)
<IntegerPart><.><NonRepeatingPart> (e.g. 0.5, 1., 2.12, 2.0001)
<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)> (e.g. 0.1(6), 0.9(9), 0.00(1212))

The repeating portion of a decimal expansion is conventionally denoted within a pair of round brackets. For example:

1 / 6 = 0.16666666… = 0.1(6) = 0.1666(6) = 0.166(66)

Both 0.1(6) or 0.1666(6) or 0.166(66) are correct representations of 1 / 6.

Example 1:

Input: S = "0.(52)", T = "0.5(25)"
Output: true
Explanation:
Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

Example 2:

Input: S = "0.1666(6)", T = "0.166(66)"
Output: true

Example 3:

Input: S = "0.9(9)", T = "1."
Output: true
Explanation: 
"0.9(9)" represents 0.999999999... repeated forever, which equals 1.  [See this link for an explanation.]
"1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".

Note:

Each part consists only of digits.
The <IntegerPart> will not begin with 2 or more zeros. (There is no other restriction on the digits of each part.)
1 <= <IntegerPart>.length <= 4
0 <= <NonRepeatingPart>.length <= 4
1 <= <RepeatingPart>.length <= 4

Solution1: Expend the string

Extend the string to 16+ more digits and covert it to double.

0.9(9) => 0.99999999999999
0.(52) => 0.525252525252525
0.5(25) => 0.5252525252525

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

bool isRationalEqual(string S, string T) {

auto convert = [](string s) {

// 0.1234(567)

// 01234567890

// i = 1, p = 6

auto i = s.find('.');

auto p = s.find('(');

if (p != string::npos) {

string r = s.substr(p + 1, s.length() - p - 2);

s = s.substr(0, p);

while (s.length() < 16)

s += r;

}

return stod(s);

};

return abs(convert(S) - convert(T)) < 1e-10;

}

};

Python3

class Solution:

def isRationalEqual(self, S, T):

def convert(s):

i = s.find('.')

p = s.find('(')

if p >= 0:

r = s[p+1:-1]

s = s[0:p]

while len(s) < 16:

s += r

return float(s)

return abs(convert(S) - convert(T)) < 1e-10

Solution 2: Convert to a friction number

C++

// Author: Huahua, running time: 24 ms.

class Friction {

public:

Friction(long n = 0, long d = 1) {

long g = __gcd(n, d);

n_ = n / g;

d_ = d / g;

}

Friction operator+(const Friction& o) const {

return Friction(n_ * o.d_ + d_ * o.n_, d_ * o.d_);

}

bool operator==(const Friction& o) const {

return this->n_ * o.d_ == this->d_ * o.n_;

}

private:

long n_;

long d_;

};

class Solution {

public:

bool isRationalEqual(string S, string T) {

auto convert = [](string s) {

std::regex re("(\\d+)\\.?(\\d+)?(\\((\\d+)\\))?");

std::smatch matches;

std::regex_match(s, matches, re);

string int_part = matches[1].str();

string nr_part = matches[2].str();

string r_part = matches[4].str();

Friction f(stoi(int_part), 1);

const int base = pow(10, nr_part.length());

if (nr_part.length())

f = f + Friction(stoi(nr_part), base);

if (r_part.length())

f = f + Friction(stoi(r_part), (pow(10, r_part.length()) - 1) * base);

return f;

};

return convert(S) == convert(T);

}

};

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

}

};