Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Excel Sequence Generator

Problem: Write some code to print the below sequence from 0 to N.
The sequence runs from A to Z and then it starts again by appending an A to the sequence.

Hint: This is the decimal system extended to alphabets.

Solution: This looks similar to a hexadecimal encoding problem where the base is 26 instead of 16.

Where hexadecimal has characters from '0' to '9' and then 'A' to 'F' representing 10 to 15,

Our base-26 encoding appears to be having characters from 'A' to 'Z' which should represent 0 to 25.

Only problem with the above logic is that it does not account for '0' (zero)

If 'A' stands for '0', then 'Z' would stand for 25.

Then next word in sequence would be 'AA' which should stand for 26 but it does not.

The base-26 conversion logic makes it equivalent to '0' too. (0*26 + 0)

To solve this, let us first introduce a '0' in the encoding and make it base-27
Once that is settled, we will remove the cases for '0' from that encoding to get the desired result.

Base-27 encoding Base-26 encoding
------------------------------------------------------->
Check the base-27 class first to understand how '0' is removed from base-26 one.
------------------------------------------------------->
```public class ExcelBase27
{
public static void main(String[] args)
{
String test[] = {"A", "B", "Z", "AA", "AZ", "ZZ",
"AAA", "BDFGHS", "ZZZ", "ZSERTU", "XXX"};

for (String s : test)
{
int num = getNumber(s);
String s2 = getSequence(num);
System.out.println(s + " = " + num + " = " + s2);
}

for (int i=1; i<2626; i++)
{
if (i%27==1)
System.out.println();
System.out.print(getSequence(i) + " ");
}
}

static int getNumber (String s)
{
char[] chars = s.toUpperCase().toCharArray();
int n = 0;
for (char c : chars)
{
n = 27*n;
// Although zero will never come as a char,
// This if condition is only put to show that
// its a base-27 encoding
if (c != '0')
n += (c - 'A' + 1);
}
return n;
}

static String getSequence (int num)
{
String s = "";

while (num != 0)
{
char c;
int remainder = num%27;
if (remainder == 0)
c = '0'; // Will never happen
else
c = (char)('A' + remainder-1);

num = num/27;
s = c + s;
}
return s;
}
}
```
```public class ExcelBase26
{
public static void main(String[] args)
{
String test[] = {"A", "B", "Z", "AA", "AZ", "ZZ",
"AAA", "BDFGHS", "ZZZ", "ZSERTU", "XXX"};

for (String s : test)
{
int num = getNumber(s);
String s2 = getSequence(num);
System.out.println(s + " = " + num + " = " + s2);
}

for (int i=1; i<2626; i++)
{
if (i%26==1)
System.out.println();
System.out.print(getSequence(i) + " ");
}
}

static int getNumber (String s)
{
char[] chars = s.toUpperCase().toCharArray();
int n = 0;
for (char c : chars)
{
n = 26*n;

//if (c != '0')
n += (c - 'A' + 1);
}
return n;
}

static String getSequence (int num)
{
String s = "";

while (num != 0)
{
char c;
int remainder = (num-1)%26;
//if (remainder == 0)
//    c = '0';
//else
c = (char)('A' + remainder);
num = num - (num-1)%26;
num = num/26;
s = c + s;
}
return s;
}
}
```
Output Output
```A = 1 = A
B = 2 = B
Z = 26 = Z
AA = 28 = AA
AZ = 53 = AZ
ZZ = 728 = ZZ
AAA = 757 = AAA
BDFGHS = 30947014 = BDFGHS
ZZZ = 19682 = ZZZ
ZSERTU = 383281059 = ZSERTU
XXX = 18168 = XXX
```
```A = 1 = A
B = 2 = B
Z = 26 = Z
AA = 27 = AA
AZ = 52 = AZ
ZZ = 702 = ZZ
AAA = 703 = AAA
BDFGHS = 25701071 = BDFGHS
ZZZ = 18278 = ZZZ
ZSERTU = 317698909 = ZSERTU
XXX = 16872 = XXX
```

The base-26 version is not very easy to understand.
So it might make sense to understand only the base-27 version.
The output of both the functions is same though, only difference is that the integer value generated by base-27 is higher but that is an internal detail, invisible to the user.

The base-26 needs to be understood if lowest integer value (corresponding to a sequence) is desired.

Note that the base-27 encoding is not continuous and has holes for all multiples of 27
Example: for n=27, getSequence() returns 'A0' which is not a valid sequence in the above.
But again, this is an internal detail, invisible to the user dealing with valid sequences always.

Best way to understand this is to draw an analogy with the decimal number system.
Decimal (or even octal or hexadecimal) number system always have '0' as a valid character.
Hence they do not have such holes (Like 10 comes after 9 in decimal and A0 comes after F in hexadecimal)
So the enlightening moment of this problem is the understanding that '0' is not a valid character in this.
Its a base-27 problem with a special handling for zeroes.

An interestingly question at this point is:
If 26 alphabets can be encoded using base-27, can we encode any m-symbol alphabet by base-N encoding (where N > m)?

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: