O(log n) Programming

Question

I am trying to prepare for a contest but my program speed is always dreadfully slow as I use O(n). First of all, I don't even know how to make it O(log n), or I've never heard about this paradigm. Where can I learn about this?

For example,

If you had an integer array with zeroes and ones, such as [ 0, 0, 0, 1, 0, 1 ], and now you wanted to replace every 0 with 1 only if one of it's neighbors has the value of 1, what is the most efficient way to go about doing if this must occur t number of times? (The program must do this for a number of t times)

EDIT: Here's my inefficient solution:

import java.util.Scanner;

public class Main {

static Scanner input = new Scanner(System.in);

public static void main(String[] args) {

    int n;
    long t;

    n = input.nextInt();
    t = input.nextLong();
    input.nextLine();

    int[] units = new int[n + 2];
    String inputted = input.nextLine();
    input.close();
    for(int i = 1; i <= n; i++) {
        units[i] = Integer.parseInt((""+inputted.charAt(i - 1)));
    }

    int[] original;

    for(int j = 0; j <= t -1; j++) {
        units[0] = units[n];
        units[n + 1] = units[1];
        original = units.clone();

        for(int i = 1; i <= n; i++) {
            if(((original[i - 1] == 0) && (original[i + 1] == 1)) || ((original[i - 1] == 1) && (original[i + 1] == 0))) {
                units[i] = 1;
            } else {
                units[i] = 0;
            }
        }

    }

    for(int i = 1; i <= n; i++) {
        System.out.print(units[i]);
    }
}

}

Answer 1

As I was saying in the comments, I'm fairly sure you can keep out the array and clone operations.

You can modify a StringBuilder in-place, so no need to convert back and forth between int[] and String.

For example, (note: This is on the order of an O(n) operation for all T <= N)

public static void main(String[] args) {
    System.out.println(conway1d("0000001", 7, 1));
    System.out.println(conway1d("01011", 5, 3));
}

private static String conway1d(CharSequence input, int N, long T) {
    System.out.println("Generation 0: " + input);

    StringBuilder sb = new StringBuilder(input); // Will update this for all generations

    StringBuilder copy = new StringBuilder(); // store a copy to reference current generation
    for (int gen = 1; gen <= T; gen++) {
        // Copy over next generation string
        copy.setLength(0);
        copy.append(input);

        for (int i = 0; i < N; i++) {
            conwayUpdate(sb, copy, i, N);
        }

        input = sb.toString(); // next generation string
        System.out.printf("Generation %d: %s\n", gen, input);
    }

    return input.toString();
}

private static void conwayUpdate(StringBuilder nextGen, final StringBuilder currentGen, int charPos, int N) {
    int prev = (N + (charPos - 1)) % N;
    int next = (charPos + 1) % N;

    // **Exactly one** adjacent '1'
    boolean adjacent = currentGen.charAt(prev) == '1' ^ currentGen.charAt(next) == '1';
    nextGen.setCharAt(charPos, adjacent ? '1' : '0'); // set cell as alive or dead
}

For the two samples in the problem you posted in the comments, this code generates this output.

Generation 0: 0000001
Generation 1: 1000010
1000010
Generation 0: 01011
Generation 1: 00011
Generation 2: 10111
Generation 3: 10100
10100