Pregunta de entrevista

Entrevista de Software Engineer

-Barcelona

Skyscanner

Write function to calculate sum of first N powers of 2 starting from 1. You shouldn't use any built-in function for calculating power. Implement the most efficient solution.

Respuesta

Respuestas de entrevistas

4 respuestas

0

//This method takes O(nLog(n)) private static int sum(int n) { int sum=0; for(int i=1;i<=n;i++) { sum += power(i, 2); } return sum; } private static int power(int base, int exp) { if(exp==0) return 1; int temp = power(base, exp / 2); if(exp%2==0) return temp * temp; else return base * temp * temp; }

Shayan en

0

You can do this with bitwise operations. The way to come to the solution is by making a table of the calculations in binary. N Sum Sum(bin) 1 2 10 2 6 110 3 14 1110 The progression becomes apparent and then you just need to figure out a way of getting that number with bitwise operations. ((1 Gives 1 followed by N zeros ((1 Makes the above into 1s (minus one spot) ((1 Adds a zero at the end by moving everything one step to the left

Anónimo en

0

You can do this with bitwise operations. The way to come to the solution is by making a table of the calculations in binary. N Sum Sum(bin) 1 2 10 2 6 110 3 14 1110 The progression becomes apparent and then you just need to figure out a way of getting that number with bitwise operations. `((1 Gives 1 followed by N zeros `((1 Makes the above into 1s (minus one spot) `((1 Adds a zero at the end by moving everything one step to the left

Anónimo en

0

2^1 + 2^2 + 2^3 + ... + 2^n = 2^(n+1) - 2 thus int sum(int n) { return (1<<(n+1)) - 2; }

d en

Añadir respuestas o comentarios

Para publicar un comentario sobre esto, inicia sesión o regístrate.