Math Archives - Page 11 of 23 - Huahua's Tech Road

花花酱 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 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 1363. Largest Multiple of Three

By zxi on February 23, 2020

Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.

Since the answer may not fit in an integer data type, return the answer as a string.

If there is no answer return an empty string.

Example 1:

Input: digits = [8,1,9]
Output: "981"

Example 2:

Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:

Input: digits = [1]
Output: ""

Example 4:

Input: digits = [0,0,0,0,0,0]
Output: "0"

Constraints:

1 <= digits.length <= 10^4
0 <= digits[i] <= 9
The returning answer must not contain unnecessary leading zeros.

Solution: Greedy + Math + Counting sort

Count the numbers of each digit.
if sum % 3 == 0, we can use all digits.
if sum % 1 == 0, we can remove one digits among {1, 4, 7} => sum % 3 == 0
if sum % 2 == 0, we can remove one digits among {2, 5, 8} => sum % 3 == 0
if sum % 2 == 0, we have to remove two digits among {1, 4, 7} => sum % 3 == 0
if sum % 1 == 0, we have to remove two digits among {2, 5, 8} => sum % 3 == 0

Time complexity: O(n)
Space complexity: O(n) w/ output, O(1) w/o output

C++

// Author: Huahua

class Solution {

public:

string largestMultipleOfThree(vector<int>& digits) {

vector<int> c(10);

for (int d : digits) ++c[d];

auto getNum = [&](const vector<int>& ds) {

for (int d : ds) --c[d];

string ans;

for (int d = 9; d >= 1; --d) ans.append(c[d], '0' + d);

ans.append(ans.empty() ? min(1, c[0]) : c[0], '0');

return ans;

};

const int r = accumulate(begin(digits), end(digits), 0) % 3;

vector<vector<int>> rs{{0, 3, 6, 9}, {1, 4, 7}, {2, 5, 8}};

// Use all digitis.

if (r == 0) return getNum({});

// Remove one among {1, 4, 7}, {2, 5, 8}

for (int d : rs[r]) if (c[d]) return getNum({d});

// Remove two among {1, 4, 7}^2 (r = 2), {2, 5, 8}^2 (r = 1)

for (int d1 : rs[3 - r])

for (int d2 : rs[3 - r])

if (d1 == d2 && c[d1] > 1 || d1 != d2 && c[d1] && c[d2])

return getNum({d1, d2});

return "";

}

};

Python3

# Author: Huahua

class Solution:

def largestMultipleOfThree(self, digits: List[int]) -> str:

c = collections.Counter(digits)

def getNum(ds):

ans = []

for d in ds: c[d] -= 1

for d in range(9, 0, -1): ans += [d] * c[d]

ans += [0] * min(1 if not ans else c[0], c[0])

return ''.join(map(str, ans))

rs = [[0, 3, 6, 9], [1, 4, 7], [2, 5, 8]]

r = sum(digits) % 3

if r == 0: return getNum([])

for d in rs[r]:

if c[d] > 0: return getNum([d])

for d1, d2 in zip(rs[3 - r], rs[3 - r]):

if d1 == d2 and c[d1] >= 2 or d1 != d2 and c[d1] and c[d2]:

return getNum([d1, d2])

return ""

花花酱 LeetCode 1362. Closest Divisors

By zxi on February 23, 2020

Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.

Return the two integers in any order.

Example 1:

Input: num = 8
Output: [3,3]
Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.

Example 2:

Input: num = 123
Output: [5,25]

Example 3:

Input: num = 999
Output: [40,25]

Constraints:

1 <= num <= 10^9

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

vector<int> closestDivisors(int num) {

auto divisors = [](int n) {

for (int i = sqrt(n); i >= 2; --i)

if (n % i == 0) return vector<int>{i, n / i};

return vector<int>{1, n};

};

auto ans1 = divisors(num + 1);

auto ans2 = divisors(num + 2);

return ans1[1] - ans1[0] < ans2[1] - ans2[0] ? ans1 : ans2;

}

};

Python3

# Author: Huahua

class Solution:

def closestDivisors(self, num: int) -> List[int]:

def divisors(n: int) -> List[int]:

for i in range(int(math.sqrt(n)), 1, -1):

if n % i == 0: return [i, n // i]

return [1, n]

a1, a2 = divisors(num + 1), divisors(num + 2)

return a1 if a1[1] - a1[0] < a2[1] - a2[0] else a2

花花酱 LeetCode 1344. Angle Between Hands of a Clock

By zxi on February 13, 2020

Given two numbers, hour and minutes. Return the smaller angle (in sexagesimal units) formed between the hour and the minute hand.

Example 1:

Input: hour = 12, minutes = 30
Output: 165

Example 2:

Input: hour = 3, minutes = 30
Output: 75

Example 3:

Input: hour = 3, minutes = 15
Output: 7.5

Example 4:

Input: hour = 4, minutes = 50
Output: 155

Example 5:

Input: hour = 12, minutes = 0
Output: 0

Constraints:

1 <= hour <= 12
0 <= minutes <= 59
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: Math

Compute the angle of the hour hand (h + m / 60.0) * 360 / 12 as a_h
Compute the angle of the minute hand m / 60.0 * 360 as a_m
ans = min(abs(a_h – a_m), 360 – abs(a_h – a_m))

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

C++

// Author: Huahua

class Solution {

public:

double angleClock(int hour, int minutes) {

double a_m = minutes * 360 / 60;

double a_h = (hour + minutes / 60.0) * 360 / 12;

return min(abs(a_m - a_h), 360 - abs(a_m - a_h));

}

};

Posts published in “Math”

花花酱 LeetCode 1390. Four Divisors

Solution: Math

C++

花花酱 LeetCode 365. Water and Jug Problem

Solution: Math

C++

花花酱 LeetCode 1363. Largest Multiple of Three

C++

Python3

花花酱 LeetCode 1362. Closest Divisors

Solution: Brute Force

C++

Python3

花花酱 LeetCode 1344. Angle Between Hands of a Clock

C++