Posts tagged as “math”

花花酱 LeetCode 2119. A Number After a Double Reversal

By zxi on December 26, 2021

Reversing an integer means to reverse all its digits.

For example, reversing 2021 gives 1202. Reversing 12300 gives 321 as the leading zeros are not retained.

Given an integer num, reverse num to get reversed1, then reverse reversed1 to get reversed2. Return true if reversed2 equals num. Otherwise return false.

Example 1:

Input: num = 526
Output: true
Explanation: Reverse num to get 625, then reverse 625 to get 526, which equals num.

Example 2:

Input: num = 1800
Output: false
Explanation: Reverse num to get 81, then reverse 81 to get 18, which does not equal num.

Example 3:

Input: num = 0
Output: true
Explanation: Reverse num to get 0, then reverse 0 to get 0, which equals num.

Constraints:

0 <= num <= 10⁶

Solution: Math

The number must not end with 0 expect 0 itself.

e.g. 1230 => 321 => 123
e.g. 0 => 0 => 0

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

C++

// Author: Huahua

class Solution {

public:

bool isSameAfterReversals(int num) {

return num == 0 || num % 10;

}

};

花花酱 LeetCode 1922. Count Good Numbers

By zxi on December 25, 2021

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).

For example, "2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, "3245" is not good because 3 is at an even index but is not even.

Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 10⁹ + 7.

A digit string is a string consisting of digits 0 through 9 that may contain leading zeros.

Example 1:

Input: n = 1
Output: 5
Explanation: The good numbers of length 1 are "0", "2", "4", "6", "8".

Example 2:

Input: n = 4
Output: 400

Example 3:

Input: n = 50
Output: 564908303

Constraints:

1 <= n <= 10¹⁵

Solution: Fast Power

Easy to see that f(n) = (4 + (n & 1)) * f(n – 1), f(1) = 5

However, since n is huge, we need to rewrite f(n) as 4^n/2 * 5^(n+1)/2 and use fast power to compute it.

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

C++

// Author: Huahua

constexpr int kMod = 1e9 + 7;

long long modPow(long long base, long long n) {

long long ans = 1;

while (n) {

if (n & 1) ans = (ans * base) % kMod;

base = (base * base) % kMod;

n >>= 1;

}

return ans;

}

class Solution {

public:

int countGoodNumbers(long long n) {

return (modPow(4, n / 2) * modPow(5, (n + 1) / 2)) % kMod;

}

};

花花酱 LeetCode 202. Happy Number

By zxi on December 5, 2021

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2³¹ - 1

Solution: Simulation

We can use a hasthable to store all the number we generated so far.

Time complexity: O(L)
Space complexity: O(L)

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

unordered_set<int> s;

while (n != 1) {

if (!s.insert(n).second) return false;

n = getNext(n);

}

return true;

}

};

Optimization: Space reduction

Since the number sequence always has a cycle, we can use slow / fast pointers to detect the cycle without using a hastable.

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

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

int slow = n;

int fast = getNext(n);

do {

slow = getNext(slow);

fast = getNext(getNext(fast));

} while (slow != fast);

return slow == 1;

}

};

花花酱 LeetCode 201. Bitwise AND of Numbers Range

By zxi on December 5, 2021

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

Constraints:

0 <= left <= right <= 2³¹ - 1

Solution: Bit operation

Bitwise AND all the numbers between left and right will clear out all the low bits. Basically this question is asking to find the common prefix of left and right in the binary format.

5 = 0b0101
7 = 0b0111
the common prefix is 0b0100 which is 4.

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

C++

// Author: Huahua

class Solution {

public:

int rangeBitwiseAnd(int left, int right) {

while (right > left)

right &= (right - 1); // clears the lowest set bit.

return right;

}

};

花花酱 LeetCode 171. Excel Sheet Column Number

By zxi on November 28, 2021

Given a string columnTitle that represents the column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

Example 1:

Input: columnTitle = "A"
Output: 1

Example 2:

Input: columnTitle = "AB"
Output: 28

Example 3:

Input: columnTitle = "ZY"
Output: 701

Example 4:

Input: columnTitle = "FXSHRXW"
Output: 2147483647

Constraints:

1 <= columnTitle.length <= 7
columnTitle consists only of uppercase English letters.
columnTitle is in the range ["A", "FXSHRXW"].

Solution: Base conversion

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

C++

// Author: Huahua

class Solution {

public:

int titleToNumber(string s) {

int ans = 0;

for (int i = s.length() - 1, cur = 0; i >= 0; --i) {

cur = cur ? cur * 26 : 1;

ans += (s[i] - 'A' + 1) * cur;

}

return ans;

}

};

Posts tagged as “math”

花花酱 LeetCode 2119. A Number After a Double Reversal

Solution: Math

C++

花花酱 LeetCode 1922. Count Good Numbers

Solution: Fast Power

C++

花花酱 LeetCode 202. Happy Number

Solution: Simulation

C++

Optimization: Space reduction

C++

花花酱 LeetCode 201. Bitwise AND of Numbers Range

Solution: Bit operation

C++

花花酱 LeetCode 171. Excel Sheet Column Number

Solution: Base conversion

C++

Related Problems