Close

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…

Forming the nth binary sequence

A binary sequence contains 0 and 1 only S.No  Binary sequence——————–1     02     13     004     015     10…Given a number k, we have to design an algorithm to print kth binary sequence. Initial approach (not efficient): Starting from the sequence 0, this algorithm iterates k times. To get the next sequence, in each iteration we do the following. check the last…

Next Round – A problem from Codeforces

This problem is from Codeforces. If you want to solve this problem on your own, follow this link. Here is the simplified problem statement. Given a list of scores of contestants in a competition, arranged in decreasing order. We have to calculate the number of people qualified for the next round.This is determined as follows,…

Finding the right most occurence of an element in a sorted array

Given an array of sorted numbers, we have to find the right most occurrence of a number.For example given an array {1,2,2,2,3}, the right most occurrence of 2 is at index 3 (0-based index). This post is related to one of my previous posts ( Finding the left most occurrence in sorted array).Similar to the…

Finding the integer square root of a number

How do we implement a function to find the integer square root of a number? For example int_sqrt(4) = 2, int_sqrt(10) = 3. (We have to take floor of the actual square root) A simple method is to iterate i from 1 to N/2 and keep checking until i2 < N, and whenever i2 >=…

Finding an element in a circularly sorted array

Given a circularly sorted array, how to search for an element efficiently? For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3. Since the array is sorted but rotated, we can expect it to be solved using the binary search technique. We can design an…

How many times a sorted array is rotated?

Given a circularly sorted array of unique elements, how do we efficiently find the number of rotations? For example the array [4, 5, 1, 2, 3] is (right) rotated twice. Before proceeding to find a solution, let’s note some observations. To find the number of rotations, we have to find the smallest element in the…

Finding the magic index of the array

Given a sorted array of distinct values, how do you find an index i such that array[i] = i? Let us call it a magic index.For example if the given array is [-23, -4, 2, 19, 56]. Element 2 is found at array[2]. So the output is 2.If there no such element in the array…

Finding a number in a sorted array with the least difference from given number

Given a sorted array and a value, we have to find the closest value (with least difference). For example let the input array be {-2, 4, 7, 11, 17} and the input number is 10, the output should be 11. This problem is actually a variation of binary search where in we have to find…