Devise an algorithm to find whether a given number N is of the form 2^x + 2^y (^ means exponentiation, x and y are positive).
Click here to see the solution.
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.
Courtesy: Vibhaj
Hints: No hints will be provided for this problem. Think more buddy, Yes! you can. |
|
Solution:
The solution is using bitmaps (arrays of bits)
1. Initialization will take O(N) but checking for existence will be done in O(1)
2. Bitmap array will be char[M/8] since a char is 8 bits long
Complexities :
Time : O(N) in initialization, O(1) in access
Space : O(M)
Code :
// init() is called once for all numbers in list one by one to initialize the bitmap
void init(int[] bitmap, int M, int num){
int base = num/8;
int offset = 1 << (n%8);
bitmap[base] |= offset;
}
bool exists(int[] bitmap, int M, int num){
int base = num/8;
int offset = 1 << (n%8);
return (bitmap[base] & offset);
}
|
|
|
Posts
