Please help me with FCTRL and FCTRL2

Hello,
First of all thanks for the initative, i am new on this website and enjoy the challenges so far.
I have some issues with these 2 beginner problems : FCTRL and FCTRL2. I have browsed the Forum already but I did not find anything relevant that might help me. I mainly code in Java and I am not an expert, the issues I am having are :

  • Wrong answer for FCTRL.
  • Too much time for FCTRL2.

In both case it takes at lest 2 minutes for the tests to compute and to send me a response.

I don’t really see what is wrong in my code as I get the good answers for the examples given in the problem wording and it is fast.

Here are my programs :

FCTRL :

import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.Scanner;

    public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter stdout = new PrintWriter(System.out);
		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			BigDecimal value = new BigDecimal(sc.nextInt());		
			int trailingZeros = 0;
			while (value.divide(new BigDecimal("5")).compareTo(new BigDecimal("1")) == 1) {
				trailingZeros += value.divide(new BigDecimal("5")).intValue();
				value = value.divide(new BigDecimal("5"));
			}
			stdout.println(trailingZeros);
		}
		sc.close();
		stdout.flush();
		stdout.close();
	}
}

FCTRL2 :

import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	public static BigInteger[] compute(int max){
		BigInteger[] nFact = new BigInteger[max];
		nFact[0] = new BigInteger("1");
		for (int i = 1; i < max; i++) {
			nFact[i] = nFact[i-1].multiply(new BigInteger(i+1+""));
		}
		return nFact;
	}
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter stdout = new PrintWriter(System.out);
		int n = sc.nextInt();
		List<Integer> values = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) values.add(sc.nextInt());
		int max = Collections.max(values);
		BigInteger[] nFact = compute(max);
		for (int i = 0; i < n; i++) {
			stdout.println(nFact[values.get(i)-1]);
		}
		sc.close();
		stdout.flush();
		stdout.close();
	}
}

I really hope someone can help me ! Thanks !

EDIT :
For FCTRL to work I had to change the condition

value.divide(new BigDecimal("5")).compareTo(new BigDecimal("1")) == 1

in the while loop by :

value.divide(new BigDecimal("5")).compareTo(new BigDecimal("1")) == 1 || value.divide(new BigDecimal("5")).compareTo(new BigDecimal("1")) == 0

Hello dear, your FCTR code has one small error-

For factorials where the zero is first encountered, your code prints 0.

Eg, take 2!,3!,4! - they have no zeroes.

The firs trailing 0 comes in 5!. But your code is printing 0 for it. However, for 6!, it prints fine.

Here are the input and output results of your code-

Compilation Successful
Input (stdin)
2
5
6
Your Output
0
1

If you can explain your algo in both codes, like what you did or what your thought process, i can help you further (not much acquainted with java).

As for FCTRL, big integer is supposed to give you TLE. The problems etter wanted you to do some clever implementation (Its actually a medium level problem).

Links to algorithm -

-Find factorial of 100
-Finding factorial of large number in c++

Just look at how they implemented it, and try to do it on your own. You should be able to understand it as the psedo codes are kind of same.

Hi,
Thanks for the quick answer. I think i know where the issue was in FCTRL, I’ve modified my code and am currently running the verification. I am using BigDecimal though which might lead to TLE. I’ll try to switch back to double as it might be precise enough in the case BigDecimal does not work.
For FCTRL2, I find it weird that it gives me TLE as I ran it multiple time locally and it gave me an answer instantly. even it the worst case (100 inputs of the number 100) it was an instant answer.
I thought the complexity was not too bad as I only compute the largest number’s factorial and store all steps in an array. This way if I want to get any factorial of a number I just have to access its position in the array…

Anyway I’ll try to reproduce the code you’ve given and post an update here.

@vijju123 i’m also gettign TLE in may17 for the same solution which reported to be WA before… am i the only one who’s getting this error

After reuploading FCTRL2 this morning, it was a VA, and time of execution was 0.07 ! So I guess it was related to the servers being slow to compute.

Problem links have been added.

Your computer gave correct output, within stipulated time? Hmm, then i dont think TLE should had been there. Since you are using pre-computation, i too think that its the way to go (i mistook your algo to be computing every numbers factorial from scratch, sorry for that!)

Anyways, waiting for your update before beginning any further investigation :).

Alright, so FCTRL gave me AC after the tiny modification; so that’s done. I can maybe send my code for FCTRL2 again but with detailed comments on the way it works ?

EDIT: You can get my commented progra; using this pastebin link https://pastebin.com/qwf16xFr

I ran your code on worst case. It worked in 0.13 seconds. Moreever, i am seeing worse time algorithms pass too. I see people reporting that in contest also, some are getting unnecessary TLE, so i will suggest that you try aain submitting tomorrow MORNING (as load on server should be less at that time)

Alright I’ll do that thanks :wink:

No, in the thread “Codechef submissions are very slow” (Its in front page only), people said that they tested it. They wrote program which only took input, and reported to get TLE, so i feel its server issue.

Thanks for confirmation dear. :slight_smile:

I have done this question using recursion in java. i hope it helps,
suggestions are welcomed.

import java.io.;
import java.util.
;
import java.text.;
import java.math.
;
import java.util.regex.*;

class Solution {

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    while(t--!=0) {
        System.out.println(factorial(Integer.parseInt(br.readLine())));
    }
}

public static BigInteger factorial(Integer n){    
    BigInteger result = BigInteger.valueOf(n);
    BigInteger one = new BigInteger("1");
    
    if(n<2) {
        return one;
    }
    
    return result.multiply(factorial(n-1));
}

}