Single Number

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.

Example:
I/P = [1, 2, 3, 2, 3, 1, 3]
O/P = 3

Approach: Take xor of all the elements. The number of terms occurring even number of times get cancelled due to property of xor that a ^ a = 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14

#include<iostream> using namespace std; int main(){ int arr[] = {2, 3, 3, 3, 3, 4, 2, 4, 4, 2, 4}; //{1, 2, 4, 4, 10, -8}; int n = sizeof(arr)/sizeof(arr[0]); int result = 0; for(int i = 0 ; i < n ; i++ ){ result = result ^ arr[i]; } cout << result << " is the odd time occurring element!" << endl; return 0; }

Read More

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of 1 bits it contains.

Example:

The 32-bit integer 11 has binary representation 00000000000000000000000000001011, so the output should be 3.

Approach: The efficient method is to use an unsigned number and keep left shifting it 32 times and keeping the ones count if a one is found at the current bit position.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include<iostream> using namespace std; int num1Bits(unsigned int a){ if(a <= 0){ return 0; } int count = 0; while(a != 0){ if(a%2 == 1){ count++; } a = a >> 1; } return count; } int num1BitsEfficient(unsigned int A){ int count = 0; unsigned int bit = 1; for(int i = 0; i <= 32; i++){ if(bit & A){ count++; } bit = bit << 1; } return count; } int main(){ unsigned int a = 11; cout << num1Bits(a) << endl; cout << num1BitsEfficient(a) << endl; return 0; }

Read More

Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Approach : Use xor of all the nums from 0 to n and elements of nums array.

Because of the property that  i ^ i  = 0, only missing element survives in the end.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public: int missingNumber(vector<int>& nums) { int n = nums.size(); int result = 0; for(int i = 0; i <= n; i++){ result = result ^ i; } for(int i = 0; i < n; i++){ result = result ^ nums[i]; } return result; } };

Read More

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t bit = 1; uint32_t result = 0; for(int i = 0; i <= 32; i++ ){ if(bit & n){ //if n has 1 at this bit, then set this bit from the reverse result = result | (1 << 32 - i - 1); } //left shift bit by 1 each time bit = bit << 1; } return result; } };

Read More