Category Archives: Number theory

Minimum number of squares formed from a rectangle

Given a rectangle of some length and width, How do you divide them into minimum number of squares? This is a problem from Codechef.

For example give a rectangle of size 2 x 4, we can make them into two squares of 2 x 2.
Similarly a rectangle of size 3 x 7, can only be divided into 21 squares each of size 1 x 1.

So what is the logic behind this?
The length and width should be divided in same equal parts, and that part should as greater as possible. So we have to find the GCD(Greatest Common Divisor) of the length and width of the rectangle. Then the minimum number of squares can be calculated by
l/g * w/g. where l = length, w = width, g = GCD(l,w)

Here is the C++ code which implements this.

How to check if a given number is Fibonacci number

How to check if the given number is a Fibonacci number?

A Fibonacci series starts with 0, 1. Remaining elements are formed by adding previous two numbers.

Here are a few Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…

If a number is given, a straight forward way to check if it is a Fibonacci number is to generate the numbers one by one until we get the required number or greater than that.
Here is the python code do that.
One more approach is based on a property of Fibonacci numbers
If 5*x2+4 or 5*x2-4 (or both) is a perfect square, we can conclude that it is a Fibonacci number. 

The C++ code is given below.



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;
  }

Printing the prime factorization of a given number

How do we write a program to find the prime factorization of a given number?
For example prime factorization for 18 can written as 2 * 3 * 3 or 2 * 3 ^ 2.
For any number there is only one possible prime factorization. 
An efficient algorithm can be given as follows. we run a loop with i ranging from 2 to sqrt(n). In each iteration, we try to reduce the number by dividing it with i as many times as possible. As we examined in the last post, we can find all the factors of a number by checking the divisibility of it from 1 to square root of n itself.
Here is the C++ code to do this.

Finding all the factors of a given number

Given a number, how do we write a program to find all of it’s factors or divisors.
For example, for the number 18, the factors are {1, 2, 3, 6, 9, 18}.

An immediate algorithm that comes to our mind is to run a loop from 1 to n. In each iteration check if the counter divides the number n. If it divides print it.
for( i = 1; i <= n; i++ )
{
if( n % i == 0 )
cout << i << " ";
}

But this approach runs for n iterations. we can do better than this. One possible improvement can be to start with 1 and n as factors and run the loop from 2 to n/2. This is based on the observation that after n/2 there will not be any factors of n until n. So it is safer to stop at n/2 itself.

list.add(1);
for( i = 2; i <= n/2; i++ )
{
if( n % i == 0 )
list.add(i);
}
list.add(n);

This is clearly an improvement over the previous method because it runs only for n/2 iterations. Can we still improve this?  

Yes it is possible! This is based on the observation that the factors always appear in pairs. If a is a factor of n, then there should be some k such that a * k = n. so k must also be a factor of n. This approach runs only for sqrt(n) iterations and performs better than the previous two algorithms.

factorList.add(1);
for( i = 2; i <= sqrt(n); i++ )
{
if( n % i == 0 )
{
factorList.add(i);
if( i != sqrt(n) )
factorList.add(n/i);
}
}
factorList.add(n);