I want to collect all the numbers in the range [a, b] whose factorial starts with an even number.

For example:

a = 1, b = 10

Answer:

2 3 4 8

Explanation:

2! = 2 = starts with even
3! = 6 = starts with even
4! = 24 = starts with even
8! = 40320 = starts with even

Constraints:

1 <= a,b <= 100

Here is my code:

List<Integer> process(int a, int b) {
    long base = i;
    for(int i=1; i<=a; i  ) base *= i;
    
    if(even(base)) list.add(a);
    
    for(int i=a 1; i<=b; i  ) {
        base *= i;
        if(even(base)) list.add(i);
    }
    return list;
}

boolean even(long k) {
    int z = (""   k).charAt(0) - '0';
    return z % 2 == 0;
}

This was asked some days back in a coding challenge, when I implemented this, 6 hidden test cases were failing out of 15 test cases. I am not able to find what is the bug in this code.

CodePudding user response：

I am using BigInteger to solve this. To help speed up the process I am memoizing subsequent factorial computations as starting points for future ones. I also set up a record to hold pertinent data to facilitate the process.

There may be a mathematical way to predict the parity of the first digit but for now, this seems to work.

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class FactorialStartsWithEven {

    public static void main(String[] args) {
       
        List<Integer> list = getForRange(1, 20);
        System.out.println(list);
    }

prints

[2, 3, 4, 8, 12, 13, 14, 16, 18] 

public static List<Integer> getForRange(int start, int end) {
    List<Integer> results = new ArrayList<>();
    for (int i = start; i < end; i  ) {
       if(factorialStartsWithEven(i)) {
           results.add(i);
       }
    }
    return results;
}

Record declared to hold the data

    record Fact(BigInteger fact, int n, boolean parity) {}

Initialize the Memo for computed factorials

    static List<Fact> computed = new ArrayList<>(List.of(
            new Fact(BigInteger.ONE, 0, false),
            new Fact(BigInteger.ONE, 1, false),
            new Fact(BigInteger.TWO, 2, true)));

• If the value already exists, just look it up and return the boolean.
• else, get the last computed value and start computing up to n, adding each factorial to the list as it is computed.

    public static boolean factorialStartsWithEven(int n) {
        if (n < computed.size()) {
            return computed.get(n).parity;
        }
        Fact f = computed.get(computed.size()-1);
        BigInteger b = f.fact;
        Fact result = null;
        for (int k = f.n 1; k <= n; k  ) {
            b = b.multiply(BigInteger.valueOf(k));
            result = new Fact(b, k, Character.digit(b.toString().charAt(0),10) % 2 == 0);
            computed.add(result);
        }
        return result.parity;
    }

CodePudding user response：

Is simpler than the way you thought that.

1. Loop from a to b

2. Calc the factorial of the loop index

3. Check if the 1st character of the generated index is even and add it to your list

4. Print the list

   private static List<Integer> process(int a, int b)
   {
       List<Integer> list = new ArrayList<>();
       for (int i = a; i <= b; i  )
       {
           final int factorial = calcFactorial(i);
           if (factorialStartsWithEven(factorial))
               list.add(i);
       }
       return list;
   }
   
   private static boolean factorialStartsWithEven(int factorial)
   {
       final String strVal = String.valueOf(factorial);
       final int intVal = Integer.valueOf(strVal.charAt(0));
       return intVal % 2 == 0;
   }
   
   private static int calcFactorial(int n)
   {
       if (n == 0)
           return 1;
       return (n * calcFactorial(n - 1));
   }