Close

## Duplicate elements in array at given distance

Given an array of numbers A, which might contain duplicate elements,  How do we find if there are two elements A[i], A[j] such that i, j are distinct and the difference between them is at most k? Look at the following examples.1. A = [9, 5, 6, 9, 3, 0, 1], K =3The answer is…

## Longest sub array with zero sum

Given an array of integers (positive and negative), how do we find a longest sub-array with zero sum? For example, consider the example [5, 0, -1, 3, -2, 4], the longest sub array with zero sum contains 4 elements.  The straight forward approach is to check the sum of all possible arrays and find out…

## Programming puzzle – calculating product array

Given an array of numbers A[1:N], we have to generate a product array P[1:N] such that P[i] contains the product A[1]*…A[i-1]*A[i+1]…A[N] That means each entry in the product array should contain product off all the elements except the one at that particular index. For example let us consider the array [4, 2, 10, 5], the…

## Standing Ovation: Google codejam 2015 Qualification round problem

Every year Google conducts a competition called Codejam for programming enthusiasts. The qualification round for the year 2015 got finished yesterday. In this post, I am going to explain the solution approach for the first problem.You can read the problem from this link. I will try to give the abridged problem statement below. There are…

## Searching for an element in array with successive elements atmost 1 distance apart

Given an array of integers where each element has a difference of atmost 1 with it’s neighbors, we need to find the given element. For example, consider the array [1, 2, 2, 1, 2, 3, 2, 1], and the element to be searched is 3, we need to return the index 5. This is just…

## Maximum number of 1s in any row of a boolean matrix

Given a matrix consisting of only 0,1s, with each of it’s row sorted (i.e all 0s appear before 1s). The problem is to efficiently find the maximum number of 1s present in any row. For example consider the following matrix. 0 0 1 10 0 0 10 1 1 10 0 0 0 The maximum…

## Finding the maximum element in a bitonic array

Given an array in which the elements are increasing up to a point and then decreases (this is also called a bitonic array), how do we efficiently find the maximum element?For example, the input arrays can look like {1, 3, 5, 4, 2} ,  {11, 17, 25, 36, 24, 6}. Basically we need to find…

## Minimum number of chages to make equal groups

Given an array of numbers, how do we find the minimum number of changes(additions/subtractions) to the elements so that each number in the array is same or equal. For example given the array {1, 2, 3, 4}, the minimum number of changes are 3. i.e we can choose any of the four elements and make…

## Maximum length of subarray with non-zero elements

Given an array of of size N, How do we find the longest sub-array with all non-zero elements? For example consider the array {34, 0, 18, 3, 0, 1, 4, 5, 0, 12}, the longest sub-array with non-zero elements is 3 i.e {1,4,5}. This problem is from Codechef. Follow this link to solve this problem…

## Finding a sub list with least max-min difference – Codeforces puzzle

This is a problem from Codeforces. Please follow this link to solve this problem on your own. The abridged problem statement is as follows. You are given an list of numbers, and sub-list size as input. The challenge is to find a sub-list such that the difference between the maximum and minimum numbers in that…