8.4 Numerical Processing
504. Base 7
Problem Description
Given a decimal integer, convert it to its base-7 representation.
Input and Output Example
Input a decimal integer and output a string representing its base-7 format.
Input: 100
Output: "202"
In this example, 100 in base-7 comes from 100 = 2 * 49 + 0 * 7 + 2 * 1.
Solution Explanation
For base conversion
problems, division and modulus (mod) are typically used for calculations. Special attention is needed for edge cases such as negative numbers and zero. If the output is expected as a numeric type rather than a string, consider whether it might exceed integer bounds.
- C++
- Python
string convertToBase7(int num) {
if (num == 0) {
return "0";
}
string base7;
bool is_negative = num < 0;
num = abs(num);
while (num) {
int quotient = num / 7, remainder = num % 7;
base7 = to_string(remainder) + base7;
num = quotient;
}
return is_negative ? "-" + base7 : base7;
}
def convertToBase7(num: int) -> str:
if num == 0:
return "0"
base7 = ""
is_negative = num < 0
num = abs(num)
while num:
quotient, remainder = num // 7, num % 7
base7 = str(remainder) + base7
num = quotient
return "-" + base7 if is_negative else base7
172. Factorial Trailing Zeroes
Problem Description
Given a non-negative integer, determine how many trailing zeroes are in its factorial result.
Input and Output Example
Input a non-negative integer and output a non-negative integer representing the number of trailing zeroes in the factorial result.
Input: 12
Output: 2
In this example, 12! = 479001600 has two trailing zeroes.
Solution Explanation
Each trailing 0 is produced by a factor of 2 × 5 = 10. Therefore, we can decompose each element in the factorial into its prime factors and count how many 2s and 5s there are. It is evident that the number of factor 2s is far greater than the number of factor 5s, so we only need to count the number of factor 5s in the factorial result.
- C++
- Python
int trailingZeroes(int n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
def trailingZeroes(n: int) -> int:
return 0 if n == 0 else n // 5 + trailingZeroes(n // 5)
415. Add Strings
Problem Description
Given two strings composed of digits, find their sum as a result.
Input and Output Example
Input consists of two strings, and output is an integer representing the sum of the input numbers.
Input: num1 = "99", num2 = "1"
Output: 100
Since addition proceeds from right to left, the strings can be reversed first, then calculated digit by digit. This type of problem tests attention to details, such as carrying and handling different string lengths.
Solution Explanation
- C++
- Python
string addStrings(string num1, string num2) {
string added_str;
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int len1 = num1.length(), len2 = num2.length();
if (len1 <= len2) {
swap(num1, num2);
swap(len1, len2);
}
int add_bit = 0;
for (int i = 0; i < len1; ++i) {
int cur_sum =
(num1[i] - ’0’) + (i < len2 ? num2[i] - ’0’ : 0) + add_bit;
added_str += to_string(cur_sum % 10);
add_bit = cur_sum >= 10;
}
if (add_bit) {
added_str += "1";
}
reverse(added_str.begin(), added_str.end());
return added_str;
}
def addStrings(num1: str, num2: str) -> str:
added_str = ""
num1 = num1[::-1]
num2 = num2[::-1]
len1, len2 = len(num1), len(num2)
if len1 <= len2:
num1, num2 = num2, num1
len1, len2 = len2, len1
add_bit = 0
for i in range(len1):
cur_sum = int(num1[i]) + (int(num2[i]) if i < len2 else 0) + add_bit
added_str += str(cur_sum % 10)
add_bit = int(cur_sum >= 10)
if add_bit:
added_str += "1"
return added_str[::-1]
326. Power of Three
Problem Description
Determine whether a number is a power of 3.
Input and Output Example
Input an integer, output a boolean value.
Input: n = 27
Output: true
Solution Explanation
There are two methods. One is using logarithms. Let log3 n = m, if n is an integer power of 3, then m must be an integer.
- C++
- Python
bool isPowerOfThree(int n) {
return fmod(log10(n) / log10(3), 1) == 0;
}
def isPowerOfThree(n: int) -> bool:
return n > 0 and math.fmod(math.log10(n) / math.log10(3), 1) == 0
Another method is that, within the range of a C++ int
, the maximum power of 3 is . If n
is an integer power of 3, then 1162261467 % n
must equal zero; otherwise, it is not. However, in Python, since int
can theoretically represent arbitrarily large numbers, we can only use a loop to verify.
- C++
- Python
bool isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
def isPowerOfThree(n: int) -> bool:
if n <= 0:
return False
while n % 3 == 0:
n //= 3
return n == 1
50. Pow(x, n)
Problem Description
Compute x
raised to the power n
.
Input and Output Example
Input a floating-point number x
and an integer n
, output a floating-point number representing the result of the power computation.
Input: x = 2.00000, n = 10
Output: 1024.00000
Solution Explanation
Using recursion, we can solve this problem relatively easily. Pay attention to handling edge cases.
- C++
- Python
double myPow(double x, int n) {
if (n == 0) {
return 1;
}
if (x == 0) {
return 0;
}
if (n == numeric_limits<int>::min()) {
return 1 / (x * myPow(x, numeric_limits<int>::max()));
}
if (n < 0) {
return 1 / myPow(x, -n);
}
if (n % 2 != 0) {
return x * myPow(x, n - 1);
}
double myPowSqrt = myPow(x, n >> 1);
return myPowSqrt * myPowSqrt;
}
def myPow(x: float, n: int) -> float:
if n == 0:
return 1
if x == 0:
return 0
if n < 0:
return 1 / myPow(x, -n)
if n % 2 != 0:
return x * myPow(x, n - 1)
myPowSqrt = myPow(x, n >> 1)
return myPowSqrt * myPowSqrt