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...
Category: Bit Manipulation
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...
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:...
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...
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...
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...
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...
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:...
Number of bit to be flipped to convert one number to another.
Objective: 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...
All elements appears thrice and one element appears once. Find that element in O(n) time and O(1) space
Objective: 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...
Find the only element in array which appears only once
Objective: 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:...
Number of 1’s in bit representation of a number
Objective: Write an algorithm to count the number of 1’s in the bit representation in given number. Example: Number: 6 Output: 2 ( 1 1 0) Number: 11 Output: 3 ( 1 0 1 1)...
Find the right most unset bit OR zero bit of a number
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...
Find the two repeating elements in a given array | 6 Approaches
Objective: Given an array of n+2 elements. All elements of the array are in range 1 to n and all elements occur once except two numbers which occur twice. Write an algorithm to find...
Find the right most set bit of a number
Objective: Given a number, write and algorithm to find the right most set bit in it (In binary representation). Example: Number : 1 Binary representation: 1 Position of right most set bit: 1 Number...