[Note: The problem mentioned below are not so hard to solve if we ignore the restricted complexities. Also there are other methods to solve this problems, this post is about solving this problems using bit-manipulation.]
Problem 1: Given an array where every element occurs two times or in general even no of times except the one element which occurs only once or in general odd number of times. Find that element. The time and space Complexity of the solution must be O(N) and O(1) respectively.
The key concept here is bitwise-xor (^).
some properties of xor:
(i) The xor of a number with itself is Zero. i.e. a ^ a = 0
(ii) The xor of a number with Zero is the same number. i.e. a ^ 0 = a;
(iii) Associativity i.e. a ^ (b ^ c) = (a ^ b) ^ c;
so in the given array if we do the bitwise xor of entire array, the numbers occurring even number of times will become zero. And the number occurring only odd number of times will xor with zero to result into itself.
Ex.
(i) A = [ 3, 3, 4, 4, 7, 7, 5].
xor_of_A = 3 ^ 3 ^ 4 ^ 4 ^ 7 ^ 7 ^ 5 = 5;
(ii) B = [3, 5, 3, 5, 6, 6, 6];
xor_of_B = 3 ^ 5 ^ 3 ^ 5 ^ 6 ^ 6 ^ 6 = 6;
here's my code:
Problem 1: Given an array where every element occurs two times or in general even no of times except the one element which occurs only once or in general odd number of times. Find that element. The time and space Complexity of the solution must be O(N) and O(1) respectively.
The key concept here is bitwise-xor (^).
some properties of xor:
(i) The xor of a number with itself is Zero. i.e. a ^ a = 0
(ii) The xor of a number with Zero is the same number. i.e. a ^ 0 = a;
(iii) Associativity i.e. a ^ (b ^ c) = (a ^ b) ^ c;
so in the given array if we do the bitwise xor of entire array, the numbers occurring even number of times will become zero. And the number occurring only odd number of times will xor with zero to result into itself.
Ex.
(i) A = [ 3, 3, 4, 4, 7, 7, 5].
xor_of_A = 3 ^ 3 ^ 4 ^ 4 ^ 7 ^ 7 ^ 5 = 5;
(ii) B = [3, 5, 3, 5, 6, 6, 6];
xor_of_B = 3 ^ 5 ^ 3 ^ 5 ^ 6 ^ 6 ^ 6 = 6;
here's my code:
Problem 2: Given an array where every element occurs three times , except one element which occurs only once. Find the element that occurs once.
Expected time and space complexities are O(N) and O(1) respectively.
If we follow the previous problem approach , since each element in the array is occurring odd number of times, it will yield the xor of all the element in the array.
The idea here is to store the elements that occurred once and twice in two separate variables "ones" and "twos" and as we encounter an element third time we remove that element from ones and twos, continue this process for all the element. At the end the variable "ones" will have the element that occured once.
The variable "ones" and "twos" here are storing the xor of the element occuring ones and twice respectively.
To summarize, basically for every element we xor it with the "ones" and store the result to "ones".
If the number is repeated (twice) then we remove it from "ones" and xor it with "twos" an store the result to "twos". If that number if repeated third times we remove it from "twos". At the end the unique element is left in the variable "ones".
Expected time and space complexities are O(N) and O(1) respectively.
If we follow the previous problem approach , since each element in the array is occurring odd number of times, it will yield the xor of all the element in the array.
The idea here is to store the elements that occurred once and twice in two separate variables "ones" and "twos" and as we encounter an element third time we remove that element from ones and twos, continue this process for all the element. At the end the variable "ones" will have the element that occured once.
The variable "ones" and "twos" here are storing the xor of the element occuring ones and twice respectively.
To summarize, basically for every element we xor it with the "ones" and store the result to "ones".
If the number is repeated (twice) then we remove it from "ones" and xor it with "twos" an store the result to "twos". If that number if repeated third times we remove it from "twos". At the end the unique element is left in the variable "ones".
No comments:
Post a Comment