Find whether a given number N is of the form 2^x + 2^y (^ means exponentiation, x and y are positive).

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).

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)

// 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);
}