Why do i get SIGSEGV error in this submission?

The link to problem : [FCTRL][1]

My solution : [Solution][2]

I am getting a SIGSEGV error on submission. Please help!!!
[1]: FCTRL Problem - CodeChef
[2]: CodeChef: Practical coding for everyone

First of all, you don’t have to calculate the factorial of n.

The answer is same as the power of 5 in the prime factorization of n.

The fctrl function is wrong, it will go into an infinite loop for all n>1

2 Likes

Some things you need to see in your code-

A zero is added for every additional 5x2 in product. In case no. of 5 and 2 are unequal, no. of 0 are min(no of 5, no of 2)
(Take example of 5x2 ,5x5x2)

In factorial, no. of 5 in product is always <no of 2 in prduct

Calculating factorials is never an option due to overflow.

Manually find number of 0 for small cases and find pattern. Take sample case of - 4! 5! 10! 11! 20!

Then note additional example from 25! 30! 50! (In 25, 2 additional 5 are added instead of usual one as 25=5x5)

2 Likes

@vijju123 what’s wrong with this corrected code now?

/* PROB - FCTRL */

#include <stdio.h>

int nozfctrl(int num);

int main(void) {
	// your code goes here
	int t=0;
	scanf("%d\n", &t);
	int n=0, i=0;
	for(i=1;i<=t;++i)
	{
	    scanf("%d\n", &n);
	    printf("%d\n", nozfctrl(n));
	}
	return 0;
}

int nozfctrl(int num)
{
    int zeroes = 0, five=0, two=0, i=0;
    for(i=1;i<=num;++i)
    {
        while(1)
        {
            int j=i;
            if(j%2==0)
            {
                j/=2;
                ++two;
                continue;
            }
            if(j%5==0)
            {
                j/=5;
                ++five;
                continue;
            }
            break;
        }
    }
    zeroes = (five>two)?two:five;
    return zeroes;
}

Plz help!!!

@vijju123, now this code gets a TLE. What to do?

/* PROB - FCTRL */

#include <stdio.h>

int main(void) {
	// your code goes here
	int t;
	scanf("%d\n", &t);
	while(t--)
	{
	    int i=0,count=0,num;
	    scanf("%d\n", &num);
	    for(i=5;i<=num;++i)
	    {
	        int n=i;
	        while(n>0)
	        {
	            if(n%5==0)
	            {
	                n/=5;
	                ++count;
	            }
	            else
	                break;
	        }
	    }
	    printf("%d\n", count);
	}
	return 0;
}

Thanks in advance.

@vijju123, to check every number between 1-num (i’m taking 5-num coz there are no 5s in 1-4) and the inner loop reduces the number by division with 5 and breaks when it is not divisible by 5.

Example :

For N=10, 

outer loop starts from 5. A dry run would be as follows: 

i=5
n=5
5>0 - T
5%5=0 - T
n=1
count=1
i=6
n=6
6>0 - T
6%5=0 - F
i=7
n=7
7>0 - T
7%5=0 - F
i=8
n=8
8>0 - T
8%5=0 - F
i=9
n=9
9>0 - T
9%5=0 - F
i=10
n=10
10>0 - T
10%5=0 - T
n=2
count=2
i=11

Ok, i got your logic. You are generating all numbers from 5 to that number, and incrementing 5. It is correct, but it takes lot of time.

The observation you need to make is that SINCE its factorial, till the number is >=5, there is ATLEAST 1 5 in it. If you read this carefully-

Take example of 24! . How many 5 does it have in product? It has 4 '5' in product (5, 10(=5x2), 15(=5x3) and 20). But your code is adding only 1.

Then you will find the correct way to find number of 5 quickly.

Here is your code, a bit modified getting AC-

https://www.codechef.com/viewsolution/13891982

Look at the idea of getting number of 5. Lets take some examples-

5! = 1 '5'
6!= 6/5=1 '5'
15!= 15/5 = 3 '5'
25! = 25/5 +1 (as 25=5x5, so 2 5s are getting added instead of 1) = 6 '5'

Also, 25/5 =5 . 

Hypothesis : Their can be some connection between n being >5 and number of '5' in product.

If i try 30! now,

30! = 30/5 +1 = 7 '5'

What about 50! ?

50! = 50/5 +2 = 12 '5' . (Logic- 5,10,15,20,30,35,40,45 add 1 '5' each. 25 and 50 (=25x2) add 2 '5' each. Sum is 12)

Hint- Try to use your brute force program to verify such things!!)


I then took examples of higher cases like 125, and came to conclusion that-

Look at 50.

Let no. of five be denoted by f.

50/5 = 10. so f+=10.

10 is STILL >5. Also 10/5 is 2, which on adding to f gives the required answer!  Some playing with sample cases will prove that this, indeed, is the correct way to find the no. of '5'.
This gives us the algo that-
while(number>0)
{
number_of_5 +=number/5;
number=number/5;
}
This much is enough! 

I see that you work really hard. You just need to sharpen that ‘perception’ of yours. Once you do that, you will get an intuition of what to do. Keep practicing, its a bit of struggle initially. Then you get used to it by practice and master it. Then again the cycle repeats when you start another topic.

2 Likes

@vijju123 help plz.

thanks. i got the problem.

thanks. u are great :slight_smile:

You are close, there is just minor bug you failed to notice.

1)I said that in factorials, number of 2 will ALWAYS be more than no. of 5. Use it to save your time! You dont need to find how many twos are there.

Take example of 24! . How many 5 does it have in product? It has 4 ‘5’ in product (5, 10(=5x2), 15(=5x3) and 20). But your code is adding only 1!.

The correct implementation is-

while(j%5==0)
{
five+=j/5;
j=j/5;
}

Comment in case it doesnt help!

Ok, give me some time. Checking it out :slight_smile:

1 Like

Hey dear! Can you please explain the purpose of-

for(i=5;i<=num;++i)

thanks @vijju123. i understood your solution. a nice approach.

P.S.- Suggested Edit - 30! = 30/5 +1 = 7 ‘5’ (not 6 ‘5’)

ooops :stuck_out_tongue: XD