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).
In a previous post “Allocating multidimentional array at runtime in C” I have explained a technique to allocate multidimensional arrays on runtime. While playing around with OpenMPI, I came to know that while sending/receiving a buffer, it requires the elements of a 2d matrix (or any dimension) to be in adjacent. Basically it does not care what you send, or receive, what it cares is the number of elements to be send should be adjacent to one another. In the previous post, the process will allocate the 2d or n-d matrix, but the rows of the matrix may not be adjacent to each other, as each row was allocated separately with malloc and then inserted into another array of pointers, each of which location points to the base addresses of these memory block. Read the post for details.
In C language the 2d array/matrix are stored in a row-major order, that is the elements of the matrix are stored adjacent to each other in the memory row wise. The first row comes first then just after the first row the second row starts, and so on. In the previous method the rows of the matrix may be scattered throughout the memory, as they are allocated with seperate malloc calls, but each of these returned addresses to the memory blocks (used as rows) are assigned to another array of pointers, which holds the rows together, and allows the mat[i][j] syntax to work.
For the applications in which, we might need to allocate the matrix dynamically at runtime, also have the rows of the matrix requires to be adjacent in the memory, and also make the mat[i][j] syntax work can be fulfilled by the following approach.
Continue reading “Dynamically allocating 2d array with adjacent rows in memory”
Arrays in C language are static in nature, and cannot be resized at runtime. The effect of runtime allocation of an array could be achieved by hierarchically allocating blocks of memory at runtime. Below we discuss the mechanism to allocate multidimensional arrays.
Continue reading “Allocating multidimentional array at runtime in C”