Bit Manipulation

Question 1

(Easy) Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]

Output: 1

Answer 1

Approach: Bit Manipulation

Concept

If we take XOR of zero and some bit, it will return that bit

a⊕0=a

If we take XOR of two same bits, it will return 0

a⊕a=0

a⊕b⊕a=(a⊕a)⊕b=0⊕b=b

So we can XOR all bits together to find the unique number.

public int singleNumber(int[] nums) {
int res = 0;
for (int i : nums) {
res ^= i;
}
return res;
}

Question 2

(Easy) Missing Number

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

Example 1:

Input: [3,0,1]

Output: 2

Answer 2

We can harness the fact that XOR is its own inverse to find the missing element in linear time.

Algorithm:

Therefore, if we initialize an integer to n and XOR it with every index and value, we will be left with the missing number.

public int missingNumber(int[] nums) {
int missing = nums.length;
for (int i = 0; i < nums.length; i++) {
missing ^= i ^ nums[i];
}
return missing;
}

Question 3

(Easy) Find the Difference

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Input: s = “abcd” t = “abcde”

Output: e

Answer 3

public char findTheDifference(String s, String t) {
int res=0;int i=0;
for(i=0;i< s.length();i++){
res ^= (int)(s.charAt(i)-‘a’)^(int)(t.charAt(i)-‘a’);
}
res^= (int)(t.charAt(i)-‘a’);
return (char)(res+97);
}