algoadvance

Leetcode 504. Base 7

Problem Statement

Given an integer, return its base 7 string representation.

Clarifying Questions

1. Range of Integer: What is the range of the input integer?
   • The typical integer range in C++ can be from -2,147,483,648 to 2,147,483,647.
2. Output: Should negative numbers be handled, and if so, should the result string include a negative sign?
   • Yes, handle negative numbers by including a negative sign in the resulting string.

Strategy

1. Edge Case Handling:
   • If the input integer is 0, return "0" directly.
2. Negative Number Handling:
   • If the input integer is negative, record this information and make the number positive for easier conversion.
3. Conversion Process:
   • Use a loop to continuously divide the number by 7 and record the remainder.
   • Append remainders in reverse order to get the correct base 7 representation.
4. Result Construction:
   • If the original number was negative, add a negative sign to the resulting string.
   • Return the constructed string.

Code

#include <iostream>
#include <string>

std::string convertToBase7(int num) {
    if (num == 0) return "0";
    
    bool isNegative = num < 0;
    num = std::abs(num);
    
    std::string result;
    while (num > 0) {
        result = std::to_string(num % 7) + result;
        num /= 7;
    }
    
    if (isNegative) {
        result = "-" + result;
    }
    
    return result;
}

int main() {
    // Test cases
    std::cout << convertToBase7(100) << std::endl;  // Output "202"
    std::cout << convertToBase7(-7) << std::endl;   // Output "-10"
    std::cout << convertToBase7(0) << std::endl;    // Output "0"
    std::cout << convertToBase7(49) << std::endl;   // Output "100"
    
    return 0;
}

Time Complexity

• Time Complexity: The time complexity is O(log₇(n)) where n is the input number. This is due to the fact that we are dividing the number by 7 repeatedly, thus the number of iterations will be proportional to the logarithm of the number in base 7.
• Space Complexity: The space complexity is O(log₇(n)) to store the resulting string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?