Close

## 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…

## Counting triplets with given sum

Given an array of distinct numbers, how do we count the number of triplets with given sum? For example let us consider the array {5, 2, 7, 8, 4, 3} and the sum is 14, There are 3 triplets with the given sum(2,5,7)(2,4,8)(3,4,7) A brute-force algorithm will take O(n3) time. But this problem can also be…

## Number of pairs with sum less than or equal to given value

Given an array of numbers, Count the number of pairs with sum less than or equal to K For example consider the array {5, 1, 12, 3, 6},  pairs with sum <= 10 are {(1,3), (1,5), (1,6), (3,5), (3,6)}.  So there are 5 pairs with the given constraint. In one of the previous posts, we…

## Maximum sum path in two sorted arrays

Given two sorted arrays of size M and N, Find a sequence of elements from both the arrays whose sum is maximum. The sequence can begin with any of the two arrays and can jump from one array to another array if there is a common element. Let us consider the following exampleArray1 = {1,…

## Finding the longest consecutive subset

Given an array of positive and negative numbers(distinct), How do we find the length of the longest consecutive subset? For example consider the below array {3, 6, 1, 2, 5, 7, 8} It contains {5,6,7,8} as the longest consecutive subset. So the answer is 4. Similarly for {2, 4, 6, 8}, the answer is 1…

## Finding increasing triplet in an array

Given an array of distinct numbers, we have to find if there is any triplet of type (A[i], A[j], A[k]) such that A[i] < A[j] < A[k] and i < j < k. For example consider the array {6, 1, 5, 2, 4} We have a triplet {1, 2, 4} which satisfies the given criteria.…