Decimal to Factorial and Back in Java

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; } }
Code language: Java (java)

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; } }
Code language: Java (java)

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; } }
Code language: Java (java)

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)); } } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments