Find pairs of numbers in an array with difference ‘k’

The problem statement is, an long array is given with n elements, we need to find all the pairs of numbers in this long array which have a constant difference k. I will post three methods. The first method is the brute force method and has a runtime complexity O (n2), the next method has runtime complexity O (n*log (n)), and the last one will have the runtime complexity O (n).

Continue reading “Find pairs of numbers in an array with difference ‘k’”

Find Sum (i … j) in a list

The problem is to sum the ith to jth element of a given list. The easiest solution runs in \mathcal{O}(n) time, which starts are the ith index and adds up the numbers in the list until it reaches the jth index. In this post i will show the process of calculating the sum of elements i through j both inclusive (where i \le j), which takes \mathcal{O}(1) time for finding the sum, and \mathcal{O}(n) time and space for preprocessing the given list of length n.
Continue reading “Find Sum (i … j) in a list”

Counting Rectangles in an n X m Checked Board

We have a checked board like a chess board, but instead of 8 x 8 it has a dimension of n x m . The task is to count the number of rectangles of all possible dimensions i x j in that checked board. Also the question arises how many squares of all possible dimensions are there. We will solve this problem by establishing formulas by construction. After this we can calculate the number of rectangles and squares of a Chess Board or any other such checked board.

Continue reading “Counting Rectangles in an n X m Checked Board”

All Combinations Without Repetitions

Problem : To generate all Combinations of a set of distinct elements

Before we start discussing about the implementation we will go through the basic definitions of Combinations. Then we discuss the method to generate all the Combinations with examples and descriptions. Then the source code to implement the method will be presented. Continue reading.

Continue reading “All Combinations Without Repetitions”

r-Permutations With Repetitions

Problem : To generate all r-Permutation with repetitions of a set of distinct elements

Before we start discussing about the implementation we will go through the basic definitions of Permutations. Then we discuss the method to generate r-Permutations with repetitions with examples, and at last we implement a C Language Program of the problem. Continue reading.

Continue reading “r-Permutations With Repetitions”