count

Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence. Example For simplicity, consider the data in the range 0 to 9. [Read More]

Problem: This is not a binary tree programming problem in the ordinary sense – it’s more of a math/combinatorics recursion problem that happens to use binary trees. Suppose you are building an N node binary search tree with the values 1..N. How many structurally different binary search trees are there that store those values? Solution Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)! [Read More]

Question: Write a function that determines the number of bits set to 1 in the binary representation of an integer. Method 1 - Simple method (Right shift integer until it becomes 0) Going by the brute force approach, it would be easy to come up with the following solution. If the least significant bit of a number is 1, it will return a result of 1 when we AND it with 1. [Read More]