Close

Maximum size square sub matrix with all 1s in a binary matrix

Given a matrix of size M x N which contains only 0s and 1s, How do we find the largest square sub-matrix which contains all 1s. For example in the following example, highlighted portion indicates a 3×3 square sub-matrix with all 1s. 1 0 0 1 1 0 0 1 1 1 1 1 0…

Printing the number in binary format

How do we write a program to print the binary representation of an integer?For the sake of simplicity, let us assume that the integer takes 32 bits. The integer 367 is represented in binary as follows.0000 0000 0000 0000 0000 0001 0110 1111Iterative Method:In this method we extract the bit at each of the 32…

Print a string in reverse using recursion

The following function is simply based on recursion mechanism. We write a function printReverse(). Initially we call this function by passing a pointer to the first character of the string. We keep calling this function recursively by incrementing the pointer until we reach the null character (End of the string). If we reach null, the…

Checking if a number is power of 2

Given an integer how do we check if it is a power of 2?For example 1, 2, 4, 8, 16, 32, 64, 128, 256,… are integral powers of 2.There are several methods to check if a number is a power of 2.Method#1: Using repeated division If you repeatedly divide the number by 2 (without any…

Counting the set bits in a number

Given an integer, how do we count the number of set (1) bits?For example the number 37 has 3 set bits in it’s binary representation (0010 0101) Method#1: Simple In this method we perform & operation between the number and 1 to get the last bit (Least Significant Bit or LSB). If it is 1…

Sorting the array of 0,1,2's

We have an array that contains only 0, 1 and 2. We have to write a program to sort this array.For example if the input array is [2,0,1,2,1,0,0,2], the output should be[0,0,0,1,1,2,2,2].As the first thought, we can very well use well known sorting algorithms like Quick sort, or Merge sort or Heap sort. But that…

Sorting binary array

Given an array of 0s and 1s, how do we sort them? After sorting all the 0s appear before all the 1s.For example the array [0,1,0,1,1,0,0,0,1,1] becomes [0,0,0,0,0,1,1,1,1,1]Let us look at two approaches to solve this problem. The first one is based on bucket sort and the second is more intelligent.Method#1:We can take two counts…

Finding the most occuring element ( mode) in an array

Given an array of numbers, how do we find the element which appears most number of times? In statistics this element is called mode.A simple solution is to count the frequency of all the elements in the array and select the one with maximum frequency. The outer loop selects an element, and the inner loop…

Finding the first repeated element in the array

Given an array which contains some duplicate entries, How do we find the element which appears first and is also repeated.For example let us consider the array [10, 78, 45, 39, 22, 45, 78, 61].The element 78 is repeated and it appears before all such repetitive elements. Note that, though two entries of 45 is…

How to check if two strings are anagrams of each other

Anagram of a word is nothing but rearrangement of it’s letters to form another word.For example ‘listen’ is an anagram of ‘silent’ and ‘enlist’.We have to write a function to check if two given strings are anagrams are not. We can solve this problem in two different ways. The first way is to sort the…