algoadvance

Leetcode 168. Excel Sheet Column Title

Problem Statement

Given a positive integer, return its corresponding column title as it would appear in an Excel sheet.

For example:

• 1 -> “A”
• 2 -> “B”
• 3 -> “C”
• …
• 26 -> “Z”
• 27 -> “AA”
• 28 -> “AB”

Clarifying Questions

1. Range: What is the range of integers that can be given as input?
   • Answer: The input is a positive integer, so from 1 to a very large upper limit (likely within the range of typical 32-bit integers).
2. Output: Do we need to handle any specific edge cases such as the lowest or highest values of input?
   • Answer: Handle standard cases correctly; 1 maps to “A”, 2 to “B”, etc. A robust algorithm will naturally handle very large inputs.

Strategy

1. Analogy to Number Systems: This problem can be thought of as converting numbers into a 26-base system where the digits are A to Z. However, it deviates slightly since it is 1-indexed rather than 0-indexed (meaning 1 -> “A” rather than 0).

2. Step-by-step Conversion:
   • While num is greater than 0:
     • Calculate the current character by using modulo operation (n - 1) % 26 to get the index for the character (0-based).
     • Append the corresponding character to the result string.
     • Update the number using integer division (n - 1) / 26.
   • Since we build the string from the least significant “digit” (rightmost) to the most significant, the final string needs to be reversed.
3. Edge Cases: The algorithm naturally accommodates all positive integers, from the smallest (1, “A”) to large numbers by appropriately chaining letters.

Code

#include <iostream>
#include <string>
#include <algorithm>

std::string convertToTitle(int n) {
    std::string result;
    while (n > 0) {
        n--;  // Adjust for 1-indexed
        result += ('A' + (n % 26));
        n /= 26;
    }
    std::reverse(result.begin(), result.end());
    return result;
}

int main() {
    std::cout << convertToTitle(28) << std::endl;  // Outputs: AB
    std::cout << convertToTitle(701) << std::endl;  // Outputs: ZY
    return 0;
}

Time Complexity

• Time Complexity: O(log₍₂₆₎(n))
  • This derives from the number of divisions required to reduce n to 0, which depends on the position length of the column title.
• Space Complexity: O(1) (excluding the space for the resulting string)
  • The space used is constant other than the space for storing the output string. The string size itself is bounded by the logarithmic number of divisions.

This approach is efficient and should handle even very large integers smoothly.

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?