Category Archives: Bit Magic

How to check if Number is a power of 2 or not

Problem: Given a number we need to tell if it is a power of two or not? Example: Input: 8 Ans: Yes Solution: Here we just need to take Bitwise and (&) of N and (N-1), if its 0, the YES else NO. Explanation For power of 2: 8 is represented in binary as 1000,… Read More »

Bitwise Sieve of Eratosthenes

Bitwise Sieve of Eratosthenes. In this post, we Implement the Bitwise Sieve of Eratosthenes. This Sieve comes handy when we want to save space and time while printing prime numbers. We will first provide the code and then explain how it works. The code given below calculates Prime Numbers till 100000000 but we only print… Read More »

Find the Missing Number

Problem: Given an array(or vector) of size N-1, that has elements in the range 1 to N, all the elements in the array are unique, we need to find the missing number. Example: a[6]={1,3,4,5,6,7} Answer= 2 Solution: Approach 1: We use the mathematical formula Sum= n*(n+1)/2 Algo: Calculate Sum using the formula. Subtract every element of… Read More »

Find the Number Occurring Odd Number of Times

Problem : We are Given an array(or vector) of integer , in which each element occurs even number of times apart from one element, which occurs odd number of times. Our job is to find the element with odd occurrence in O(n) time complexity and O(1) Auxiliary space. Example : arr[7]={1,2,1,3,4,4,2} Answer : 3 Solution: We use… Read More »