## Decimal to Binary

Given a decimal number, convert that number to its binary representation. Example:  Number: 5, binary representation: 101 Number: 8, binary representation: 1000 Number: 105, binary representation: 1101001 Solution:  Initialize a result string and while the given number is greater than 0, keep dividing it by 2 and append the remainder of division to the result … Read more

## Find the number of pairs with odd XOR

Given an array of integers, write a program to find the number of pairs for which the XOR is an odd number. Example: Input[] = {3, 2, 1} Output: 2 Note: 1 XOR 2 = 3 and 2 XOR 3 = 1 Input[] = {3, 6, 9, 4} Output: 4 Naive Approach: Use nested loops … Read more

## Hamming Distance between two given integers

Objective: Given two integers, write an algorithm to calculate the hamming distance between the integers.  Hamming Distance: Hamming distance between two integers is the number of positions at which the bits are different. Example: X = 2, Y = 4 Hamming distance: 2 2 = 0 1 0 4 = 1 0 0 There are … Read more

## Number’s Complement – 2 Approaches

Objective: Given a number N, write a program to find a complement number of the given number. Flip all the bits of a number to get the complement of that number. Example:  N = 8 Output: 7 Explanation:  N = 8, binary representation: 1 0 0 0 Flip all the bits = 0 1 1 … Read more

## Count Set bits in a given Number

Objective: Given a Number, find all the set bits in that number. Example: Number: 23 Set bits: 4 (10111) Number: 15 Set bits: 4 (1111) Number: 21 Set bits: 3 (10101) Approach: Check the last bit of number, if it is 1 then add it to the result. Right shift the number by 1. Repeat … Read more

## Multiply with power of 2 without using pow() or * operator

Objective: Given a number n and k, Calculate n * k2 without using pow() or *operator. Example: N = 3, k = 4 N*k2 = 48 Approach: Bit Manipulation Left shift the number N by k. For example, N = 3 Bit representation: 0 1 1 Left shift by k = 4 0 1 1 … Read more

## Check if Given Number is power of 2.

Objective: Given a number, write a program to find if number is power of two. Example: N = 5 Output: false. N = 8 Output: true (23) N = 512 Output: true (29) Approach: This problem can be solved in multiple ways; we will discuss three solutions here. Log2 Method Check the Remainder Convert number … Read more

## Swap two numbers using Bitwise XOR Operator

Objective– Given two numbers, swap both the numbers using XOR operators. Example: X = 4, Y = 8 Output: X = 8, Y= 4 Approach: XOR operator There are many ways to swap two numbers but here we will discuss a solution to swap numbers using XOR(^) operator. Say numbers are x and y. Do … Read more

## Divide with power of 2 without using pow() or / operator

Objective: Given a number n and k, Calculate n / k2 without using pow() or / operator. Example: N = 48, k = 4 N/k2 = 3 Approach: Bit Manipulation Right shift the number N by k. N = 48 Bit representation: 0 1 1 0 0 0 0 Right shift by k = 4 … Read more

## Left Shift (<<) and Right Shift (>>) Operators

What is Left Shift (<<) Operator: a<<b means left shift the bits of number a by b places. 3<<2 means left shift the bits of number 3 by 2 places. Result = 12 011 is the bit representation of number 3. Left shift all the bits so => 0 1 1 0 (number =6) Left … Read more

## Convert Number to base 3 String Representation

Objective: Given a number convert it to base 3 representation. Example: N = 35 Base 3 representation: 1022 N = 50 Base 3 representation: 1212 Approach: Till the number is greater than 0, keep dividing it by 3 and append remainder to the result (append it at the beginning of the result) N = 35, … Read more

## Find two non-repeating numbers in an array in O(n) time and O(1) space

Objective:  Given an array of integers which has all the repeating numbers (twice) but two numbers which are non-repeating. Write an algorithm to find out those two numbers. Example int [] arrA = {4,5,4,5,3,2,9,3,9,8}; Output: 2 and 8 Approaches: This problem is similar to problem “Find two repeating elements in an array”. There could be multiple … Read more

## Number of bit to be flipped to convert one number to another.

Objec­tive:  Given two numbers x and y. write an algorithm to find the number of bits which are to be flipped to convert number x to y. Example x = 10, Y = 20 x = 0 1 0 1 0, y = 1 0 1 0 0 So if we need to convert x to … Read more

## All elements appears thrice and one element appears once. Find that element in O(n) time and O(1) space

Objec­tive:  Given an array of integers in which all the elements are appear thrice but one which appears only one. Write an algorithm to find that element. Example int [] arrA = {6,5,3,2,4,2,5,6,3,3,6,5,2}; Output: 4 Approach: Naïve Approach: Use nested for loops and compare each element with all other elements and return the element which appears … Read more

## Find the only element in array which appears only once

Objec­tive: Given an array of integers, all the elements are appear twice but one element which appears only once. Write an algorithm to find that element. Example: int [] a = { 1,5,6,2,1,6,4,3,2,5,3}; output: 4 Approach: Brute Force: Use nested loops and compare each element in array with all other elements and track the element … Read more