Close

Counting pairs in array

Given an array A of distinct numbers, how to count the number of pairs (i,j) such that A[i] < A[j] For example, let us consider A = [2, 1, 3] the pairs are (1,2), (1,3), (2,3). So there are 3 pairs. Similarly for A = [10, 6, 9, 2], there are 6 pairs This problem…

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…

GCD queries

This problem is from Codechef January challenge. Click on the link to try this problem on your own. The problem statement is as follows. Given an array of size N and two indices L and R. We need to find the GCD (Greatest Common Divisor) of all the array elements except in the range [L,R].…

Minimum area of a square enclosing given set of points

Problem: Given a set of coordinates in a two dimensional plane, How do we find the area of a minimum square which includes all the points. The points can exist on the border also. For example consider two points (0,0), (1,2) we need a minimum 2*2 square to cover these points. Hence the area is…

Printing all K combinations from N numbers

Given two numbers N and K, how do we print all the K-combinations of numbers from the set {1,2,…N}. For example consider N = 4, K = 3, the possible combinations are [  [1, 2, 3]  [1, 2, 4]  [2, 3, 4]  [1, 3, 4] ] Let us look how to solve this combination problem.…

Implementing power function

Given the base and exponent, how do we implement the pow(base,exp) function efficiently? For example  pow(2.0,5) = 32 pow(0.4,2) = 0.16 pow(2.0,-2) = 0.25 For simplicity, let us assume that the base can be a decimal number and exponent can be any integer. A straight forward implementation that comes to mind is simply multiplying the…

Number of ways of arranging 0, 1

Given ‘N’ zeros and ‘M’ ones, In how many ways can we arrange them to form a string of length (N+M)? For example if we have 2 zeros and 2 ones, we can arrange them in 6 ways 0011, 1100, 0101, 1010, 1001, 0110 If there are N symbols to arrange, The number of ways…

Number of ways to represent an integer as sum of two squares

Given a number, we have to find out the number ways to express it in the form of sum of two integer squares.For example let us consider 25, it can be written as sum of the pairs (0,25) (9,16)24 cannot be written as a sum of any two squares.Mathematically this problem is to find the…

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…

Finding all Pythagorean triples in an array

Given an array of unique elements, Write a program to print all Pythagorean triples in it. A Pythagorean triple is a set of three numbers such that square of one number is the sum of squares of the other two. For example (3,4,5) is Pythagorean triple because 52 = 32 + 42 Consider the array {5, 6, 3,…