square numbers given in an sequence

Given a positive integer sequence of numbers in an array with common difference 2 for e.g 2 4 6 8 Now replace each number by its square. Perform the computations efficiently. I was asked this question in an interview and i gave him o(n) solut开发者_如何学运维ion using bitwise operator since it is operation in the multiples of 2.If there is any better method please suggest.

I dunno if its better but it's recursive!!! :-)

(n+2)(n+2) = n**2 + 4*n + 4 // and you got n**2

class Square
{
  public static int[] sequence(int[] array)
  {
    int[] result=new int[array.length];
    for(int i=0;i<array.length;i++)
    {
      result[i]=array[i]*array[i];
    }
    return result;
  }
}

// test cases:
// Square.sequence(new int[]{2,4,6,8})
//out put->{ 4, 16, 36, 64 }

It really depends on the interviewer, and what they think is "the right thing". If it were me, I'd think the (n << 2) + 4 were neat, but on the other hand, I'd hate to see it in my code. It takes more thinking to maintain, and there's a fair chance a good optimizer might do just as good a job.

I think the phrase "perform the operation efficiently" is probably our clue that the interviewer was looking for a fast computation. It's still O(n), but let's not forget that when you are comparing two O(n) algorithms, the coefficients start to matter again.