Problem : Find the number of trailing zeroes in the factorial of a given number. This is an interesting problem. Simple way to solve this is to find the factorial of the number and then count the number of trailing zeroes. But there is a more efficient way to find the number of trailing zeroes, without even finding the factorial of the number. The number of trailing zeroes in 5! is 1, 10! is 2, 15! is 3, 20! is 4, but 25! is 6. Then 30! is 7, 35! is 8, 40! is 9, 45! is 10 but 50! is 12 and so on. So for every multiple of 25, the number of zeroes increases by 2 and for every multiple of 5, the number of zeroes increase by 1. So any number less than 5 has 0 trailing zeroes. Any number between 5 and 10 will have 1 zero, between 10 and 15 will have 2 zeroes and so on. Here is a simple C program implementation of this algorithm. import java.io.BufferedReader; import java.io.InputStreamReader; /** * * @author blogkoder * */ public class TrailingZeroesCalculator { public static void m
Problem : Design a stack of Numbers which will give you the minimum and maximum of all the elements it contains. This problem is also known as MinStack or MaxStack problem which expects you to find only the minimum or maximum. It is restated here to capture both. A stack typically has push(), pop() and size() operations. In order to find the minimum and the maximum, we will need to iterate over the elements of the stack each time we want to find the minimum and maximum. This will result in O (n) time complexity. And typically stack does not let us iterate over the elements. Many do not know that the java.util.Stack implementation does allow it as it extends java.util.Vector. We can make it more efficient by storing the minimum and maximum as instance variables in our stack and update them when ever we push a new number on to the stack. This will result in O(1) complexity for updating the max and min when pushing new numbers on stack, but when we pop the number which is currently set a