Posts tagged as “math”

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

}

};

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

}

};

花花酱 LeetCode 1332. Remove Palindromic Subsequences

By zxi on January 26, 2020

Given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string, if it is generated by deleting some characters of a given string without changing its order.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

Input: s = "ababa"
Output: 1
Explanation: String is already palindrome

Example 2:

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "". 
Remove palindromic subsequence "a" then "bb".

Example 3:

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "". 
Remove palindromic subsequence "baab" then "b".

Example 4:

Input: s = ""
Output: 0

Constraints:

0 <= s.length <= 1000
s only consists of letters ‘a’ and ‘b’

Solution: Math

if s is empty => 0 step
if s is a palindrome => 1 step
Otherwise, 2 steps…
1. delete all the as
2. delete all the bs

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

C++

// Author: Huahua

class Solution {

public:

int removePalindromeSub(string s) {

if (s.empty()) return 0;

if (s == string(rbegin(s), rend(s))) return 1;

return 2;

}

};