Traveling Salesman Problem.

[thoshi11]

The most important part of a GSM network is so called Base Transceiver Station (BTS). These transceivers form the areas called cells (this term gave the name to the cellular phone) and every phone connects to the BTS with the strongest signal (in a little simplified view). Of course, BTSes need some attention and technicians need to check their function periodically.

ACM technicians faced a very interesting problem recently. Given a set of BTSes to visit, they needed to find the shortest path to visit all of the given points and return back to the central company building. Programmers have spent several months studying this problem but with no results. They were unable to find the solution fast enough. After a long time, one of the programmers found this problem in a conference article. Unfortunately, he found that the problem is so called "Traveling Salesman Problem" and it is very hard to solve. If we have N BTSes to be visited, we can visit them in any order, giving us N! possibilities to examine. The function expressing that number is called factorial and can be computed as a product 1.2.3.4....N. The number is very high even for a relatively small N.

The programmers understood they had no chance to solve the problem. But because they have already received the research grant from the government, they needed to continue with their studies and produce at least some results. So they started to study behavior of the factorial function.

For example, they defined the function Z. For any positive integer N, Z(N) is the number of zeros at the end of the decimal form of number N!. They noticed that this function never decreases. If we have two numbers N1<N2, then Z(N1) <= Z(N2). It is because we can never "lose" any trailing zero by multiplying by any positive number. We can only get new and new zeros. The function Z is very interesting, so we need a computer program that can determine its value efficiently.


Input
There is a single positive integer T on the first line of input (equal to about 100000). It stands for the number of numbers to follow. Then there are T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000.


Output
For every number N, output a single line containing the single non-negative integer Z(N).

Example
Sample Input:

6
3
60
100
1024
23456
8735373

Sample Output:

0
14
24
253
5861
2183837

[kVen1729]

Code:

#include<iostream>

using namespace std;


//Algorithm to calculate the number of zeroes at the end of n!
//Input: A number or integer n
//Output: The number of zeroes at the end of n!
//Concept: This is a special case de' Polignac's prime composition of n! where the prime we choose is 5.
//Author: Kishore Venkateshan
//Compiler: Microsoft Visual Studio 2010
int calcZeroes(int n)                     
{
   int numZeroes = 0;
   const int DIVIDER = 5;
   while(n!=0)
   {
      numZeroes += (int)n/DIVIDER;
      n = (int)n/DIVIDER;
   }
   return numZeroes;
}

int main()
{
   int t;
   int *input;
   int *output;
   cout<<"Enter number of cases: ";
   cin>>t;
   input = new int[t];                        //For Dynamic Memory usage
   output = new int[t];
   cout<<endl<<"Enter Inputs Line By Line: "<<endl;
   for(int i=0;i<t;i++)
   {      
      cin>>*(input+i);                     //Store inputs in a pointer array
      *(output+i) = calcZeroes(*(input+i));      //Store outputs in a seperate pointer array by                    //Executing the calcZeroes Function
   }
   cout<<endl<<"Output Line By Line: "<<endl;
   for(int i=0;i<t;i++)
   {
      cout<<*(output+i);
      cout<<endl;
   }
   delete[] input;                          //Free Memory
   delete[] output;
   return 0;
}


[thoshi11]

Brilliant! Works for the given input. I failed to understand the problem though. Would you explain the problem to me?

[kVen1729]

Brilliant! Works for the given input. I failed to understand the problem though. Would you explain the problem to me?

The initial part of the problem is the least significant part if you are just the one coding the algorithm.
Anyway here is what it means,
The BTSes need to be serviced based on a schedule.
Say the set of BTSes is {a1,a2,a3,a4,......}

There are many service team. Now each of these teams are given sporadic BTSes to service at once (one working cycle), albeit a few base condition are met.
Let the team get the following set to service at once {a3,a6,a9,a11,a13,a14}

Now this team wants to find out which is shortest path they can take to visit each one of the stations and get back to their company. This as you know is Travelling Salesman Problem and is a combinatorial problem with n! solutions to check.

Now the problem's main statement and use:
The company wanted to make sure that given 'n' tasks to the service team, they can complete it all at once.

This means they need to know the time it would take for a team to complete 'n' tasks must be found, so that they can give more tasks to lesser amount of employee teams and maximize the profit.

The only way to do that was calculate n! and not draw graphs for everything. Again when n increases the efficiency turns out to be bad.

The reason they need to calculate n!, is to see if they should go into the process of computing the possibilities of all routes.

Since n! factorial is a huge number, they thought they would inspect the number of trailing zeroes and express it as exponential number...But it was useless. Cuz eventually it turned out that only few solutions worked while others were just too horrible.

The trailing zeroes of any number's factorial, is the number of zeroes it ends with. The following explanation of the solution might help

Lets first take factorials from 4 to 10...We get
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800

What you want to do is find out the trailing zeroes or in other terms, how many times you have to divide a number by 10 before it turns into a floating point number.

That is to say, you want to know the number of times 10, 100, 1000, and so on that occur in it.

It is sufficient to check the number of times 5, 25, 125, and so on occur. The reason being the pattern you can notice from the factorials between 4 to 10 (or further 15). Every time a multiple of 5 occurs, the trailing zero shoots up by 1. The reason is rather blatant, 2 occurs almost every time, but a corresponding 5 occurs only when its multiple's factorial is the input.

Hence the use of de polignac's prime conjecture gives the number trailing zeroes.
i.e Number of trailing zeroes in n! = [n/5] + [n/25] + [n/125] + .... (until [n/(5^i)] = 0)
n = input
i = 1,2,3,....
and [] implies floor funtion

eg...Number of trailing Zeroes in 60! = [60/5] + [60/25] + [60/125] = 12 + 2 + 0 = 14.....What we got from program.

[Sponsored content]