The challenge
Coding decimal numbers with factorials is a way of writing out numbers in a base system that depends on factorials, rather than powers of numbers.
In this system, the last digit is always 0 and is in base 0!. The digit before that is either 0 or 1 and is in base 1!. The digit before that is either 0, 1, or 2 and is in base 2!, etc. More generally, the nth-to-last digit is always 0, 1, 2, ..., n and is in base n!.
Read more about it at: http://en.wikipedia.org/wiki/Factorial_number_system
Example
The decimal number 463 is encoded as "341010", because:
463 = 3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0!
If we are limited to digits 0..9, the biggest number we can encode is 10!-1 (= 3628799). So we extend 0..9 with letters A..Z. With these 36 digits we can now encode numbers up to 36!-1 (= 3.72 × 1041)
Task
We will need two functions. The first one will receive a decimal number and return a string with the factorial representation.
Note: the input number is at most a long.
The second one will receive a string with a factorial representation and produce the decimal representation.
Given numbers will always be positive.
The solution in Java code
Option 1:
public class Dec2Fact {
public static String dec2FactString(long nb) {
String res = "";
String retRes = "";
int previous = 37;
while (previous != 1){
previous--;
long fact = findFact(previous);
int coeff = (int)Math.floor(1.0 *nb / fact);
if (coeff <= 0 && res == "") continue;
res += coeff + "x" + previous + "!+";
if (coeff>9){
char letter = (char)(coeff - 10 + 65);;
retRes += letter;
} else{
retRes += coeff;
}
nb -= coeff * fact;
}
return retRes+"0";
}
public static long factString2Dec(String str) {
long sumRes = 0;
for (int i = str.length()-1; i >= 0; i--){
long currFact = findFact(str.length() - i - 1);
sumRes += Character.getNumericValue(str.charAt(i)) * currFact;
}
return sumRes;
}
public static long findFact(long x){
long res = 1;
for (int i = 1; i <= x; i++){
res*=i;
}
return res;
}
}
Option 2:
import java.util.*;
public class Dec2Fact {
public static final String translate = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static String dec2FactString(long nb) {
long count = 1;
long cur = nb;
String ret = "";
while(cur != 0L) {
ret = translate.toCharArray()[(int)(cur % count)] + ret;
cur /= count;
count++;
}
return ret;
}
public static long factString2Dec(String str) {
str = new StringBuilder(str).reverse().toString();
long ret = 0L;
long curFact = 1L;
for(int i = 1; i < str.length(); i++){
curFact *= i;
ret += curFact * translate.indexOf(str.toCharArray()[i]);
}
return ret;
}
}
Option 3:
public class Dec2Fact {
public static final String mapping = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static String dec2FactString(long nb) {
StringBuilder sb = new StringBuilder("0");
for (int i=2; nb>0; nb /= i++) sb.append(mapping.charAt((int)(nb % i)));
return sb.reverse().toString();
}
public static long factString2Dec(String str) {
long acc=0, mul=1;
for (int i=0, j=str.length()-1; j>=0; i++, j--) {
if (i > 1) mul *= i;
acc += mul * mapping.indexOf(str.charAt(j));
}
return acc;
}
}
Test cases to validate our solution
import static org.junit.Assert.*;
import org.junit.Test;
import java.util.Random;
public class Dec2FactTest {
Random randomGenerator = new Random();
@Test
public void test1() {
int r = randomGenerator.nextInt(3);
if (r == 0) {
assertEquals("A0000000000", Dec2Fact.dec2FactString(36288000));
}
}
@Test
public void test2() {
int r = randomGenerator.nextInt(2);
if (r == 1) {
assertEquals(36288000, Dec2Fact.factString2Dec("A0000000000"));
}
}
@Test
public void test3() {
int r = randomGenerator.nextInt(2);
if (r == 0) {
assertEquals("4042100", Dec2Fact.dec2FactString(2990));
}
}
@Test
public void test4() {
int r = randomGenerator.nextInt(2);
if (r == 0) {
assertEquals(2990, Dec2Fact.factString2Dec("4042100"));
}
}
@Test
public void test5() {
int r = randomGenerator.nextInt(2);
if (r == 0) {
assertEquals("341010", Dec2Fact.dec2FactString(463));
}
}
@Test
public void test6() {
int r = randomGenerator.nextInt(2);
if (r == 1) {
assertEquals(463, Dec2Fact.factString2Dec("341010"));
}
}
@Test
public void test7() {
assertEquals("14F9122694751231010", Dec2Fact.dec2FactString(8150835199999999L));
}
@Test
public void test8() {
int r = randomGenerator.nextInt(2);
if (r == 1) {
assertEquals(8150835199999999L, Dec2Fact.factString2Dec("14F9122694751231010"));
}
}
@Test
public void test9() {
assertEquals("2DCAA5842344512200", Dec2Fact.dec2FactString(1000000000000000L));
}
@Test
public void test10() {
int r = randomGenerator.nextInt(2);
if (r == 1) {
assertEquals(1000000000000000L, Dec2Fact.factString2Dec("2DCAA5842344512200"));
}
}
@Test
public void test11() {
assertEquals("1212210", Dec2Fact.dec2FactString(1001L));
}
@Test
public void test12() {
int r = randomGenerator.nextInt(2);
if (r == 1) {
assertEquals(1001L, Dec2Fact.factString2Dec("1212210"));
}
}
@Test
public void test13() {
assertEquals("26A2116333000", Dec2Fact.dec2FactString(1234567890L));
}
@Test
public void test14() {
int r = randomGenerator.nextInt(2);
if (r == 1) {
assertEquals(1234567890L, Dec2Fact.factString2Dec("26A2116333000"));
}
}
@Test
public void test15() {
assertEquals(9876543210L, Dec2Fact.factString2Dec("17747074033000"));
}
@Test
public void test16() {
int r = randomGenerator.nextInt(2);
if (r == 1) {
assertEquals("17747074033000", Dec2Fact.dec2FactString(9876543210L));
}
}
@Test
public void test17() {
assertEquals("13110", Dec2Fact.dec2FactString(45L));
}
@Test
public void test18() {
int r = randomGenerator.nextInt(4);
if (r == 0) {
assertEquals(45L, Dec2Fact.factString2Dec("13110"));
}
}
@Test
public void test19() {
assertEquals(992L, Dec2Fact.factString2Dec("1211100"));
}
@Test
public void test20() {
int r = randomGenerator.nextInt(4);
if (r == 1) {
assertEquals("1211100", Dec2Fact.dec2FactString(992L));
}
}
}