# Daily Archives: November 28, 2015

## Worm walking on a line

Given a array consisted of only 0 or 1, and a number N.
We have N times to flip 0 to 1 in array. Find the longest continuous 1 after we flipped the N zero elements. Rotation is allowed.

For example, 100100111000, n=2, the best flip is 100111111000, return 6
10001101101, n=2, the best flip is 10001111111, return 8(rotation is allowed)

The idea is to set a head and tail in array. 0 between head and tail is N. Each time, move head and tail to next 0 position, and calculate the current distance between head and tail.

Because rotation is considered, we should consider about the boundary condition specially:
when number of zero in array equal N+1, should return arr.length-1.
when number of zero is less than N+1, should return arr.length.

So I added isValid to check number of zero.

A typical process without rotation is showed below:

check my code on github: link

## power(a, n) in iteration way

Given a, n, calculate a^n in non-recursive way.

The traditional way is to use recursion to reach O(logN) solution. For iteration, we can use stack to implement the recursion process. In stack, 1 means result times a, -1 means result times result, 0 doing nothing.

Take 11 as example, the process is like:

Take 15 as example, the process is like:

Below is my code:

public static int power(int a, int n) {
// build stack
Stack s = new Stack();
while(s.peek()>1) {
int curr = s.pop();
s.push(curr%2); //1 means result should time a.
s.push(-1); //-1 means result should time result.
s.push(curr/2);
}
int result = 1;
while(!s.isEmpty()) {
int curr = s.pop();
switch (curr) {
case 1:
result = result * a;
break;
case -1:
result = result * result;
break;
}
}
return result;
}

However, this problem can be solved in O(logN) time and O(1) space. Below is a process to calculate a^9:

public static int power(int a, int n) {
int result = 1;
while(n>0) {
if(n%2==1)
result = result * a;
a = a * a;
n = n>>1;
}
return result;
}

In order to understand this solution more clearly, we can transform the exponent in binary: . We know a in the code is a base. It changes like: . And we know . In this way, we know that calculating  is similar the process to build binary 1001.  The difference is that instead doing plus, we do multiplication.

In the code, a = a* a is to enlarge the base. result = result * a is to add the base in the result.