Track2

Question 1

Find the number of trailing zeros in the factorial of ‘n’?

Answer 1

Number of trailing zeros in fact(n) = number of 5s appearing in the product 123…n .
Note : 25 => contributes two 5s, 125 contributes three 5s.
Hence,

Number of trailing zeros in fact(n) = floor(n/5) + floor(n/25) + floor(n/125) + …
[every 5th number contributes one 5, every 25th number contributes two 5s, every 125th number contributes three 5s]

Question 2

Find the GCD(a, b).

Answer 2

Euclidean’s algo :- gcd(a,b) = gcd(a-b, b)

One approach is to go on making subtraction repeatedly, until one of a or b becomes 0, then return the other viz the gcd.
But more efficient approach is :-

gcd(a, b){
if(b==0)
return a;
else{
return gcd(b, a%b);
}
}

Question 3

Find the lcm of two numbers a and b.

Answer 3

Most efficient approach:-

LCM(a,b) * GCD(a, b) = a*b

Time = O( log( min(a,b) ) )

Question 4

Write a function”isPrime()” to check if a number is prime.

Answer 4

Trick to optimize the naïve approach here is : if “num” is not divisible by 2, 3, 5 it wont be divisible by 6, 8, 9, 10, etc. And we could skip checking these altogether.

Thus,
1. check if num%2 == 0
2. check if num%3==0
3. for(int i=5; i*i<=n; i=i+6){
if(num%i==0)
return false
else if(num%(i+2)==0)
return false
}
4. return true

Question 5

Write a function to list down the prime factorization of a number.

Answer 5

Trick : Similar to that used in isPrime() function.
primeFactorization(int num){

0. temp_n = num
1. while(temp_n%2==0)
   print(“2 “)
   temp_n = temp_n/2;
2. while(temp_n%3==0)
   print(“3 “)
   temp_n = temp_n/3
3. for(i=5; i*i<=num; i=i+6){
   while(temp_n%i==0){
   print(i + “ “);
   temp_n = temp_n/i;
   }

     while(temp_n%(i+2)==0){
          print(  (i+2) + " ");
          temp_n = temp_n/(i+2);
     }         } //end for }// end of function

Question 6

Given a number “num”, find all the divisors of num and print them in increasing order.
Example : num = 50
Output : 1,2,5,10,25,50.

Answer 6

allDivisors(num){
for(i=1; i*i<=n; i++){
if(num%i==0)
print(i)
}

while(i>0){
    if(num%i==0)
         print( num/i)
    
     i = i - 1;
 } }

Question 7

Given a number “num” as input, print all the prime numbers smaller than “num”.

Answer 7

We use Sieve of Eratosthenes here.
Create an array say “arr” of size (num + 1) length and initialize each element to True.
Now, run a loop from i=2 till (ii<=num).
In each iteration of the loop, we check if (arr[i] == True). If yes, we make arr[k] = False, for all k=> [2i , num ]

Once, we come out of the outer loop, if arr[i] is True, “i” is prime.

Another minor optimization to the above:- we can start k=> [ii, num] (i.e. replace 2i by i*i)

Time : O( n* loglog(n))

Question 8

Given a two numbers x and n as input, compute (x^n)

Answer 8

pow(x,n) = pow(x,n/2)*pow(x,n/2) if n is even

pow(x,n) = x*pow(x,n-1)
if n is odd

pow(x,n) = 1
if n is 0

Time = O(logn)

Question 9

Given two integers n and x, compute x^n (I e. X to the power n) iteratively in less than 0(n) time

Answer 9

This can be done using binary exponentiation.(lec13)

Say, n = 10 and x=3.
3^10 = 3^8 * 3^2

result=1
loop(n>0)
if(n%2==0)
result = resultx
x = xx
n = n/2
return result