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();
    s.add(n);
    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: power. We know a in the code is a base. It changes like: power2. And we know power3. In this way, we know that calculating power 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.