Spreadsheet Column Title
Problem
Spreadsheet columns are named A, B, ..., Z, then AA, AB, ..., AZ, BA, ... ZZ, AAA, ... Read the column number n (A is 1) and print its title. This is like a number system with 26 digits (A to Z) but without a zero, so be careful at 26, 52, 702 and so on.
Constraints
- 1 <= n <= 2147483647
Examples
Input
28
Output
AB
Input
26
Output
Z
Solutions
This is a bijective numeration: it has digits 1 to 26 and no zero. The usual 'divide and take the remainder' fails at multiples of 26 (it would give a zero digit), so we subtract 1 first. Excel allows only up to column XFD (16384), but the rule works for any n.
/*
* Problem : Column title.
* Input : One integer n.
* Output : The column title.
* Approach: Bijective base 26.
* Time : O(log n)
* Space : O(log n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String solve(long n) {
// Step 1: Build the title from the right end. There is no zero digit, so we subtract 1 before every step.
StringBuilder title = new StringBuilder();
long number = n;
while (number > 0) {
number--;
// Step 2: Now 0 means A and 25 means Z. The remainder is the last letter.
title.append((char) ('A' + number % 26));
number /= 26;
}
// Step 3: We found the letters from right to left, so reverse them.
return title.reverse().toString();
}
public static void main(String[] args) {
long n = new Scanner(System.in).nextLong();
System.out.println(solve(n));
}
}
Hints (1)
- Why do we subtract 1 in every step?