Skip to main content

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.

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;
}

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.

int trailingZeroes(int n) { 
return n == 0 ? 0 : 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

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;
}

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.

bool isPowerOfThree(int n) {
return fmod(log10(n) / log10(3), 1) == 0;
}

Another method is that, within the range of a C++ int, the maximum power of 3 is 319=11622614673^{19} = 1162261467. 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.

bool isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}

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.

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;
}