After being comfortable in loops, there are a whole lot of problems you can solve in C. I’ve been solving quite a few and here are some I found interesting. For these you need to be comfortable with the basic syntax and loops.
Problem 1:
f(x) be a function that calculates the trailing zeroes of x!(x factorial). So we need to write a program to :
- Take input for number of test cases.
- Enter first case(x).[input]
- Output f(x).
- Enter next case(x)
- Output f(x).
- This goes on till the last test case, and then the program stops.
Example
Sample Input:
6 3 60 100 1024 23456 8735373
Sample Output:
0 14 24 253 5861 2183837
Solution:
The basic idea behind computing number of zeroes in x! is to find the number of times 10 comes in the factorial’s factors. Which basically means checking the number of times 2 and 5 come (as 2*5=10) . So for this the easiest straightforward method is to find the factorial first, then keep on dividing factorial by 10 untill number(mod)10 != 0. We can define a counter for this. But the problem with this is , the limit of x is 10^9 , whose factorial will be extremely large. The datatypes in C wont be able to handle such a large number. Another problem is execution time for such a program will be enormous.
If we think a bit more closely, we see that x = x.(x-1).(x-2)….3.2.1 . So here we can count individual 2’s and 5’s from x, x-1, x-2 … uptill 1. But we see that the number of 2’s will always exceed number of 5’s in any number. So we will check for only number of 5’s, and this will give us 10’s which will give us zeroes.
To check for 5’s we can first caluculate the number of mutiples of 5 which are less than or equal to that factorial. So lets say x = 100, the multiples are 5,10,15…100. So there are 100/5 = 20 5’s present. After this we’ll check number of multiples of 25 in the number. These are 25,50,75,100 i.e 100/25 = 4. We have to add these to our total count of 5. 25 is 5^2 , which means it contains two 5’s. But we already have accounted for one 5 in the first step, hence we just add 4 directly to our previous answer. so number of 5’s uptill now : 20 + 4 = 24. Now we consider number of multiples of 5^3=125. But 125 > 100, hence no multiples. Thus our loop must stop when 5^n > x(our number). Thus we get number of zeroes.
#include<stdio.h>
int main()
{
int t, a, d, c, b; //t is the number of test cases, a is the input number, d is the counter for total number of 5’s, c is used for incrementing powers of 5, b is used for number of 5’s in one cycle of the loop.
scanf(“%d”, &t); //Enter number of test cases.
for(; t > 0; t–)
{
scanf(“\n%d”, &a); // Enter input number
d = 0 ;
c = 1 ;
for (; c <= a ; )
{
c = c * 5 ;
b = a / c ;
d = d + b ;
}
printf(“%d\n”, d) ; // Output number of 5’s = zero.
}
return 0;
}
Problem 2:
There is a job to fill n vacancies. But number of applications(x) are more than n. So the people are made to stand in a line, and are named serially from 1 to x. Then the odd numbered people are elminated. Then next again odd numbered people are eliminated. In this way the elimination continues. Compute a program (with number of test cases counter) to calculate the position in which a man should be in, so that he’s most probable to get the job.
Example
Input: 2 5 12 Output: 4 8
Solution:
The question says that only even numbered positions are entitled to go ahead. So only the 2nd, 4th, 6th …. positions will go ahead after 1st elimination. Now these terms respectively take the 1st, 2nd, 3rd… positions. Next elimination 2nd, 4th,6th… positions of this new series will go ahead(which are respectively 4th, 8th,12th terms of the original series). This will continue untill for a certain input, only 1 number is remaining.
Lets take an example by considering n = 10.
- 1 2 3 4 5 6 7 8 9 10 Position of the number 8 in the series = 8 Total terms = 10
- 2 4 6 8 10 Position of the number 8 in the series = 8/2 = 4 Total terms = 10/2 = 5 (intdiv)
- 4 8 Position of the number 8 in the series = 4/2 = 2 Total terms = 5/2 = 2(intdiv)
- 8 Position of the number 8 in the series = 2/2 = 1 Total terms = 2/2 = 1
As odd cases are being elminated in every round, the successive position of a number is equal to previous position /2 . The most favourable case will last untill the end, which in this case is 8. Hence the key to this problem seems to be to keep on successively dividing the number of people(n) by 2(n/2) untill n = 1. Hence we can setup a counter (i = 0) to count the number of times n can be divided by 2 untill n = 1. And then we can back calculate the number by continuously multiplying by 2, i times, i.e 2^i.
In this case i = 3. Hence number is equal to 2^3 = 8.
Code:
#include<stdio.h>
#include<math.h>
{
int t; //Number of test cases
int i, n, k; // i = counter that describes number of times n can be divided by 2 , n = number of persons(terms), k = final answer
scanf(“%d”, &t);
for(; t > 0 ; t–)
{
scanf(“%d”, &n);
for(i = 0 ; n > 1; i++)
{
n = n / 2;
}
k = pow(2,i);
printf(“%d\n”, k);
}
return 0;
}
TheCuriousMind94 