## Skyscanner Interview Question

Software Engineers**Country:**United Kingdom

**Interview Type:**Written Test

As requested, here's explanation:

Let's see all the powers of 2 between 1 and 4 (N=4)

```
N = 1 -> 0000010 (2^1 or 1<<1)
N = 2 -> 0000100 (2^2 or 1<<2)
N = 3 -> 0001000 (2^3 or 1<<3)
N = 4 -> 0010000 (2^4 or 1<<4)
sum -> 0011110
```

We can compute 0011110 as 0100000 - "2"

So the answer is (1<<(N+1))-2 or (2<<N)-2

Thanks for the explanation.

Is there misprint in the last row of explanation, so it should be (2<<N)-2 and not (2>>N)-2?

An implementation without Bit shift

```
public int bruteForceIt(int x){
int j = 1;
int y = 0;
for (int i = 1; i <= x; i++) {
if(x > 0){
j = j*2;
y += j;
System.out.println(j);
}
}
if(x == 0){
System.out.println("The Sum of Powers is" + 1);
return 1;
}
System.out.println("The Sum of Powers is" + y);
return j;
}
```

Using bit shift to find the powers

```
public static void bitShitForSumower(int j){
int x = 1;
int y = 0;
for (int i = 0; i < j; i++) {
//bit shift
x = x<<1;
y += x;
System.out.println("x = " + x );
}
if( j == 0) System.out.println("The Some is 1");
else { System.out.println("The some is " + y);}
}
```

Hi guys, thanks for all the answers. I was able to produce brute force solution by calculating and adding powers inside the loop without bit manipulation but my solution didn't pass timing tests, correctness tests were ok.

Is it something obvious that if i is some power of two and you do i << 1, then power gets increased by 1? It looks very elegant but I have no idea how you come up with this solution.

- smallchallenges February 02, 2015