Check if 2 trees are iso-morphic
Posted on March 24, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
Given 2 binary trees, check if they are isomorphic.
Two binary trees s and t are isomorphic if they have the same shape; the values stored in the nodes do not affect whether two trees are isomorphic.
In the diagram below, the tree in the middle is not isomorphic to the other trees, but the tree on the right is isomorphic to the tree on the left.
[Read More]Check if any number exists in the list after removing them from particular positions in natural number progression
Posted on March 24, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem
There is long list of natural numbers. Remove every 2nd no from list in 1st pass. Remove every 3rd no from list in 2nd pass. Find whether Nth natural no will exist after P passes. N and P are inputs.
Example
N is 15 and p is 3.
Initial: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
[Read More]Swap odd and even bits in an integer
Posted on March 24, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).
Input : An integer x
Output : An integer y, which odd and even bit swapped (with 0th bit being least significant bit)
Example
Input 1: 10 = 1010 Output 1: 5 = 0101 (0th bit and 1st bit have been swapped,also 2nd and 3rd bit have been swapped) Input 2: 14 = 1110 Output 2: 13 = 1101 Solution
[Read More]Avid TV watcher
Posted on March 24, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem
There is a TV avid person, who wants to spend his maximum time on TV. There are N channels that telecast programs of different length at different timings. WAP to find the program and channel number so that the person can spend his max time on TV.
Condition: If he watches a program, he watches it completely.
Example:
Channel1:
prg1: 8:00 am - 9:00am
prg2: 9:30 am - 12:00 am
[Read More]Find missing integer in an array with only access to jth bit of element A[i]
Posted on March 24, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
An array A[1..n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is ”fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer.
[Read More]Division without using *, / or % (Divide Two Integers)
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem
Divide two integers without using multiplication, division and mod operator.
Solution
Method 1 - Subtract the number until it is less then divisor
Let a be dividend and b be divisor
public int divide(int a, int b) { if(b==0) { print("\\nDivide By Zero Error"); return Integer.MIN; } int c=0; while(a>=b) // We Repeatedly Checking for the Condition a>=b { a = a - b; // Subtract b from a, and the new result stored in 'a' itself c++; // Incrementing the Count } return c; } ```This method had been discussed [here](http://k2code.
[Read More]Count total set bits in all numbers from 1 to n
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem
Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n.
Examples
Input: n = 3 Output: 4 Input: n = 6 Output: 9 Input: n = 7 Output: 12 Input: n = 8 Output: 13 Solutions
Method 1 - Simple - Count bits in individual number upto n
A simple solution is to run a loop from 1 to n and sum the count of set bits in all numbers from 1 to n.
[Read More]Next Power of 2
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem
Write a function that, for a given no n, finds a number p which is greater than or equal to n and is a power of 2.
Example
IP 5 OP 8 IP 17 OP 32 IP 32 OP 32 ```There are plenty of solutions for this. Let us take the example of 17 to explain some of them. Solutions **Method 0 : Multiply number by 2 until we find it** int power = 1;
[Read More]Count number of bits to be flipped to convert A to B
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem
You are given two numbers A and B. Write a function to determine the number of bits need to be flipped to convert integer A to integer B.
Example
Input: 73, 21 Output: 4 Representing numbers in bits : A = 1001001 B = 0010101 C = \* \*\*\* C = 4 Solution
Method 1 - Counting the bits set after XORing 2 numbers
1. Calculate XOR of A and B.
[Read More]Some useful resources
Posted on March 23, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra