Twitter online test

前几天接收到twitter的面试通知，非常意外，而且正是final的时候，没有办法，只好硬着头皮上了；在codility 上面做了两题，第一题
做出来了，第二题挂了，最终结果也挂了
第一题：

A positive integer N is given. The goal is to construct the shortest possible sequence of integers ending with N, using the following rules:

the first element of the sequence is 1; more specifically: A[0] = 1,

each of the following elements is generated by multiplying the previous element by 2 or increasing it by 1; more precisely: A = A[i−1] * 2 or A = A[i−1] + 1, for i ≥ 1.

For example, for N = 17, the shortest sequence is:

  A[0] = 1

  A[1] = 2

  A[2] = 4

  A[3] = 8

  A[4] = 16

  A[5] = 17

Write a function:

class Solution { public int solution(int N); }

that, given a positive integer N, returns the length of the shortest possible sequence of integers satisfying the above conditions and ending with N.

For example, given N = 17, the function should return 6, as explained above.

Assume that:

N is an integer within the range [1..2,147,483,647].

Complexity:

expected worst-case time complexity is O(log(N));

expected worst-case space complexity is O(1).

第二题：

是two dimesion array ，找equilibrium point.

稍后补充完整

第一题可以这样做：
int shortest(int n){
     int result = 0;
     while(n!=1 ){
          if(n % 2 !=0){
             result++;
         }
         n = n /2;
     
         result ++;
}
   
      
      return result;
        

}

第二题相当于是one dimensional array 的延伸
http://www.geeksforgeeks.org/equilibrium-index-of-an-array/
就是array中的一个值，它的上面的数加起来等于下面的，左边的数等于右边的。
找到所有的equilibrium points。
不知道有人知道怎么做嘛

DP 每个cell保存上下左右的sum，从top left ->bottom right,更新上、左，然后bottom right -> top right 更新下、右
对吗？

支持一下  期待第二题

第二题？

第一题感觉就是看二进制有几位，以及这其中几位是1.

求第二题目？

第二题涅？

感谢分享 LZ补个第二题呗～

用DP吧~~~~~~