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 Hamming Distance between two given integers

Number’s Complement – 2 Approaches

Bit Manipulation

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 Number’s Complement – 2 Approaches

Count Set bits in a given Number

Bit Manipulation

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 Count Set bits in a given Number

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

Bit Manipulation

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 Multiply with power of 2 without using pow() or * operator

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 Check if Given Number is power of 2.

Swap two numbers using Bitwise XOR Operator

Bit Manipulation

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 Swap two numbers using Bitwise XOR Operator

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 Convert Number to base 3 String Representation

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 Find two non-repeating numbers in an array in O(n) time and O(1) space

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

Bit Manipulation

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 Number of bit to be flipped to convert one number to another.

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

Bit Manipulation

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 All elements appears thrice and one element appears once. Find that element in O(n) time and O(1) space

Find the only element in array which appears only once

Bit Manipulation

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 Find the only element in array which appears only once

Number of 1’s in bit representation of a number

Bit Manipulation

Objec­tive:  Write an algorithm to count the number of 1’s in the bit representation in given number. Exam­ple: Number: 6 Output: 2 ( 1 1 0) Number: 11 Output: 3 ( 1 0 1 1)  Approach: Method 1: Run Code While number > 0 Keep doing the number & 1, increment count if result is 1 … Read more Number of 1’s in bit representation of a number

Find the right most unset bit OR zero bit of a number

Bit Manipulation

Objective: Given a number, write and algorithm to find the right most unset bit or zero bit in it (In binary representation). This problem is similar to: Find the right most set bit of a number Example: Number : 11 Binary representation: 1 0 1 1 Position of right most unset bit: 2 Number : … Read more Find the right most unset bit OR zero bit of a number