# Posts published in “Math”

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++

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++

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

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

## Python3

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)

## Python3

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

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

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

## C++

Mission News Theme by Compete Themes.