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 Decimal to Binary

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 Find the number of pairs with odd XOR

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