Category Archives: Mathematics

Last digit of a power

Given a number expressed in base, exponent form (ab) where a is arbitrary big number For example contains 100 digits, We have to write a program to find the last digit in it’s expanded form.

Eg: 45712 has a last digit of 1

Since the range of numbers is huge, it is impossible to expand the number using standard data types like int, and long. We can use library classes to calculate the exponent (Eg. BigInteger in Java), but this is will take a long time to compute the result.

For this problem, we don’t need to expand the result at all!

The trick here is to find the power of last digit in the base. The last digit in the expanded form always depends on the last digit of the base. It is always in the range of [0-9]

What if the exponent is also a big number?


We have to observe that the powers of single digit repeat after if we go on increasing the exponent.
Look at the following table. It gives a fair idea of our approach.

1 2 3 4
1 1 1 1 1
2 2 4 8 6
3 3 9 7 1
4 4 6 4 6
5 5 5 5 5
6 6 6 6 6
7 7 9 3 1
8 8 4 2 6
9 9 1 9 1

The the last digit in the power of 2 repeats every multiple of 4. Similarly the last digit in powers of 4 repeats every multiple of 2. and so on. 
Based on this observation we can write the following program to calculate the last digit in ab for arbitrary large numbers.
 

Number of rectangles

Given a number of unit squares (1 x 1). How many different rectangles can be formed with them?

For example let us consider 4 units. We can form 5 different rectangles like the following. Two rectangles are considered same if they are oriented in a different way but same dimensions.


Basically we have to arrange 1 to N-1 units to form rectangles of different dimensions.
This boils down to finding the sum of the number of pairs factors of 1 to N numbers.

Here is the C++ program to do that.

Adding a list of big numbers

Most of the popular programming languages like C/C++, Java, C# provide primitive data types (int, long) to hold values up to only a specific range.

A 64-bit integer can store only store numbers in the range of -264 to 263-1. This can store numbers containing roughly 19-20 digits.
What if we have to deal with even bigger numbers.

For example, numbers such as 1298372305835723862093487348

We have to implement our own methods to do arithmetic on such numbers. Just like the following we do for addition.

  7 8 2 9 3 4 3
  3 4 5 6 9 8 1
  1 7 6 5 2 3 5
  2 1 2 1 1 0  —->carry
—————-
1 3 0 5 1 5 5 9

In this post we will see how can we implement addition of a list of big numbers. C++ does not have a standard library data structure/algorithms to do so. How ever Java provides a BigInteger class for this purpose.

We assume that these big numbers are represented as strings.

Here is how it is implemented in C++.

Here is how it is implemented in Java. See how BigInteger made our life easier!

Number of trailing zeros in a factorial

This problem looks easy to solve for small numbers. Simply calculate the factorial and count how many zeroes are present at the end!

But the factorial grows big very fast even for small numbers which cannot fit into standard data types. (20! = 2432902008176640000. Cannot fit into a long variable also). In summary this is not the best approach that one can think of.

We can use some simple mathematical properties to solve this problem easily and efficiently. 


Can you think how can a factorial value gets a zero at the end?

If two numbers, one, a multiple 5 and and the other a multiple of 2 are multiplied, it contributes a zero at the end in the product.


For example 2*5, 14*15, 26*25 etc…
 

So our job is to calculate number of such pairs. Since the multiples of 2 will always be greater than multiples of 5, We can simply count 5-multiples which divide the given number. This is simply (number/5)

But the problem is not yet over!
How many zeroes does a 25 contribute?
Let us consider 26! = 1 * 2 * …5 * 6…*25*26
It can be re written as 
1 * 2 *…* 23 * (12* 2) * (5 * 5) * (2 * 13)
 

It contributes to two zeroes!

Similarly we can observe that 125 contributes to 3 zeroes and so on…
 

So as a conclusion, the result is the sum of 5 multiples, 25 multiples, 125 multiples etc… which are also divisors of the given number.

Here is the C++ implementation of the above solution.

Finding the integer square root of a number

How do we implement a function to find the integer square root of a number?

For example int_sqrt(4) = 2, int_sqrt(10) = 3. (We have to take floor of the actual square root)

A simple method is to iterate i from 1 to N/2 and keep checking until i2 < N, and whenever i2 >= N return i.

for( int i = 1; i <= N/2 ; i++ )
{
    if( i*i >= N )
        return i;
}

But this algorithm takes O(n) time. For large numbers this takes a lot of time. Any way to improve this further?

Binary search comes to our rescue. we start with the initial range [0, N]. In each iteration we check if mid2 <= N and (mid+1)2 >N. If this is satisfied, we return mid.

If mid2 > N, we confine our search to the left half; otherwise we search in the right half.

This implementation takes only O(log N) time.

Here is the C++ implementation. 



Computing the power of a given number

Given a base and it’s exponent, how do we efficiently evaluate it?
In other way, how do implement a pow() function which is typically provided by a library.

For example 210 = 1024.

The simplest method that comes to our mind is multiply the base with 1 in a loop for exponent times.

double result = 1;
for( i = 0; i < exp; i++ )
{
    result = result*base;
}

This method runs in O(n) time complexity where n is the exponent. 

We can make this efficient by using Divide and Conquer technique. Considering the above example, 210 can be calculated as follows.
210 = 25 * 25
25 = 22 * 22
22 = 21 * 21

In each step we avoid computing half of the product which can save us time.
Here is the C++ function to calculate the result. In this function I have handled negative exponents also. This method runs in O( log n) complexity.

  double pow(double x, int n) 
  {
        int absn = abs(n);

        if( absn == 0 )
        {
            return 1.0;
        }

        else if( absn == 1)
        {
            return (n < 0) ? (1/x) : x;
        }
       
        double temp = pow(x, absn/2);
        double result;
        
        if( absn % 2 == 0 )
        {
            result = temp*temp;
        }
        else
        {
           result = temp*temp*x;
        }
        return ( n < 0 )? (1/result) : result;
  }

Counting the number of perfect squares in a given range

Given a range of numbers, how do we count the number of perfect squares?

This problem is posted on Hackerrank as part of 20/20 Hack March 2014.

If you do not want to read the solution and you want to solve the problem on your own, Click on the link. If you want to know the solution for the problem, read on…

For example, if the given range is [1,5] the number of perfect squares in this range is 2 (including the lower and upper bounds)
1= 12 and 4 = 22
 
Simple solution:
The obvious solution is to check if each number in the given range is a perfect square or not. This runs O(n) time. For a small range of numbers, this works fine. But for a big range, this takes a lot of time.

Can we improve this solution further?
 
We can improve this as follows.
 

First we find the square roots of lower bound and and upper bounds. The difference between them gives the required number.

For example consider the range [2,11]

sqrt(2) = 1.414
sqrt(11) = 3.316

If you round them off, and take the difference (3-1), it is 2 which is the required answer.

However we have to handle two special cases.

Case 1: Lower and upper bounds are same.
For example [4, 4]. In this case we have to check if the given number is a perfect square. If it is,  output 1, otherwise output 0.

Case 2: If the lower bound is a perfect square.
In this case, we have to add 1 to the diff of square roots. 

For example consider [4, 20]; rounded square roots are [2, 4]; the diff is 2. But there are 3 perfect squares in the given range (4, 9, 16).

In all the remaining cases, the number of perfect squares is the difference of the square roots.

Here is the C++ implementation for this problem.

Generating a pascal triangle

In this post, we will write a program to generate a pascal triangle of given height.
For example, Pascal triangle of height 5 is shown below
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
The idea behind Pascal triangle is that each element in a row is the sum of left and right elements in the previous row. If the previous row does not contain left/right, they are considered as 0. The same idea is used to write simple program like the following.


Program to find GCD of two numbers

In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder – from Wikipedia
For example, the GCD of 8 and 12 is 4
Euclidian method: This is also called division algorithm. Take smallest of the two numbers and divide the other number. If the remainder is zero smaller number is the GCD. Otherwise replace the smaller number with remainder, and bigger number with present smaller number and repeat the same procedure.

Here is the step-by-step calculation

8)12(1
   8
 —-
   4)8(2
     8
    —
     0

The following c++ code implements the iterative and recursive version of Euclidian algorithm.

#include <iostream>

using namespace std;
void swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
//iterative version of Euclidian algorithm
int gcd(int x,int y)
{
while ( (y % x) != 0)
{
int r = y % x;
y = x;
x = r;
}
return x;
}
//recursive version of Euclidian algorithm
int gcd_recursive(int x, int y)
{
if( y % x == 0)
return x;
return gcd_recursive( y%x, x);
}

int main()
{
int x,y;
//read two numbers
cin>>x>>y;
//both iterative and recursive versions requires first parameter <= second
//swap if firt is greater
if( x > y )
{
swap(x,y);
}
cout<<"GCD(" << x << "," << y << ")=" << gcd_recursive(x,y) << endl;
return 0;
}