math – Page 2 – Huahua's Tech Road

花花酱 LeetCode 1447. Simplified Fractions

By zxi on May 18, 2020

Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. The fractions can be in any order.

Example 1:

Input: n = 2
Output: ["1/2"]
Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.

Example 2:

Input: n = 3
Output: ["1/2","1/3","2/3"]

Example 3:

Input: n = 4
Output: ["1/2","1/3","1/4","2/3","3/4"]
Explanation: "2/4" is not a simplified fraction because it can be simplified to "1/2".

Example 4:

Input: n = 1
Output: []

Constraints:

1 <= n <= 100

Solution: GCD

if gcd(a, b) == 1 then a/b is a simplified frication.

std::gcd is available since c++17.

Time complexity: O(n^2logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<string> simplifiedFractions(int n) {

vector<string> ans;

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

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

if (gcd(i, j) == 1)

ans.push_back(to_string(i) + "/" + to_string(j));

return ans;

}

};

花花酱 LeetCode 1390. Four Divisors

By zxi on March 22, 2020

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors.

If there is no such integer in the array, return 0.

Example 1:

Input: nums = [21,4,7]
Output: 32
Explanation:
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Constraints:

1 <= nums.length <= 10^4
1 <= nums[i] <= 10^5

Solution: Math

If a number is a perfect square (e.g. 9 = 3 * 3), it will have odd number of divisors. (9: 1, 3, 9).

Time complexity: O(sum(sqrt(num_i))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int sumFourDivisors(vector<int>& nums) {

int ans = 0;

for (int n : nums) {

int r = sqrt(n);

if (n <= 4 || r * r == n) continue;

int count = 2;

int sum = 1 + n;

for (int d = 2; d <= r; ++d)

if (n % d == 0) {

count += 2;

sum += n / d + d;

}

if (count == 4) ans += sum;

}

return ans;

}

};

花花酱 LeetCode 672. Bulb Switcher II

By zxi on March 10, 2020

There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.

Suppose n lights are labeled as number [1, 2, 3 …, n], function of these 4 buttons are given below:

Flip all the lights.
Flip lights with even numbers.
Flip lights with odd numbers.
Flip lights with (3k + 1) numbers, k = 0, 1, 2, …

Example 1:

Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]

Example 2:

Input: n = 2, m = 1.
Output: 3
Explanation: Status can be: [on, off], [off, on], [off, off]

Example 3:

Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].

Note: n and m both fit in range [0, 1000].

Solution1: Bitmask + Simulation

The light pattern will be repeated if we have more than 6 lights, so n = n % 6, n = 6 if n == 0.

Time complexity: O(m*2^6)
Space complexity: O(2^6)

C++

// Author: Huahua

class Solution {

public:

int flipLights(int n, int m) {

if (n > 6) n = n % 6 + 6;

unordered_set<int> s1{(1 << n) - 1};

auto flip = [n](int s, int start, int step) {

for (int i = start; i < n; i += step)

s ^= (1 << i);

return s;

};

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

unordered_set<int> s2;

for (int s : s1) {

s2.insert(flip(s, 0, 1));

s2.insert(flip(s, 0, 2));

s2.insert(flip(s, 1, 2));

s2.insert(flip(s, 0, 3));

}

s1.swap(s2);

}

return s1.size();

}

};

花花酱 LeetCode 365. Water and Jug Problem

By zxi on March 9, 2020

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous “Die Hard” example)

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

Solution: Math

special case 1: x == z or y == z or x + y == z: return True
special case 2: x + y < z: return False
normal case: z must be a factor of gcd(x, y)

Time complexity: O(log(min(x, y))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool canMeasureWater(int x, int y, int z) {

if (x == z || y == z || x + y == z) return true;

if (x + y < z) return false;

return z % gcd(x, y) == 0;

}

};

花花酱 LeetCode 258. Add Digits

By zxi on March 9, 2020

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

Input: 38
Output: 2 
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2. 
             Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Solution 1: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int addDigits(int num) {

int n = num;

while (n >= 10) {

int t = n;

n = 0;

while (t) {

n += t % 10;

t /= 10;

}

return n;

}

};

Solution 2: Math

https://en.wikipedia.org/wiki/Digital_root#Congruence_formula

Digit root = num % 9 if num % 9 != 0 else min(num, 9) e.g. 0 or 9

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

C++

// Author: Huahua

class Solution {

public:

int addDigits(int num) {

return num % 9 ? num % 9 : min(num, 9);

}

};

Posts tagged as “math”

花花酱 LeetCode 1447. Simplified Fractions

Solution: GCD

C++

花花酱 LeetCode 1390. Four Divisors

Solution: Math

C++

花花酱 LeetCode 672. Bulb Switcher II

Solution1: Bitmask + Simulation

C++

花花酱 LeetCode 365. Water and Jug Problem

Solution: Math

C++

花花酱 LeetCode 258. Add Digits

Solution 1: Simulation

C++

Solution 2: Math

C++