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;
    }
}

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)); 
        }
    }
}

Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments