Return the "period" size of a bit string

Question

Recently I did a very interesting online test (from Codility). Unfortunately this test was timed (30 minutes) and I ended up not being able to reach a satisfactory solution to one of the questions.

Context

A decimal number can be seen as a bit sequence.

Examples:

955 = 1110111011
10 =  1010
627 = 1001110011
102 = 1100110
104 = 1101000

These bit strings can be periodic, i.e., composed of successive bit substring repetitions.

Update

From the official definition of the problem. Given a String S composed of Q bits. The period P is the smallest positive integer such that:

• P Q / 2 and
• S[K] = S[K+P] for all K, where 0 K < Q P.

Examples:

The binary 1010 is composed of the substring 10 repeated twice. The binary 1110111011 is composed of the substring 1110 repeated two and a half times (as the 11 left at the end after two repetitions). Already the decimal 1101000 is not periodic (there is no substring with Q / 2 forming a period).

The period of a binary string is nothing more than the size of the repeating bit sequence.

955-> 1110 (período 4)
10 ->  10  (período 2)
627 -> 10011 (período 5)
102 -> 1100 (4, mas esse não é um período válido pois `P > Q / 2`)
104 -> não tem

The problem

Integer n, write an algorithm that returns the period of the binary string from n or -1 in case the binary string is not periodic:

public int periodo(int n) 

Expected complexity

• Worst temporal case O(log(N)²)
• Worst space case O(log(N))

A possible sub-optimal solution of brute force

I spent a lot of time on that question and I don’t even know if I could come up with a solution naive correct (mine feeling was that this was a bit manipulation question, in the end I ended up using Integer.toBinaryString(n) and going by brute force).

I ended up doing the following:

• Generate each candidate substring to be a period of n. Starting from 1 to [n] bit string size/ 2

   final String binaryString = Integer.toBinaryString(n);
   for (int i = 1; i < binaryString.length() / 2; i++) {
       final String period = binaryString.substring(0, i);
  

• For each of these substrings, check whether the main string could be generated from substring repeats (using a loop and comparing character to character):

  private boolean checkSolution(String binaryString, String period) {
      boolean isPeriod = true;
      for (int i = 0; isPeriod && i < binaryString.length(); i++) {
          if (binaryString.charAt(i) != period.charAt(i % period.length())) {
              isPeriod = false;
          }
      }
  
      return isPeriod;
  }
  

• Return the shortest period found (or -1 which is the default if no period has been found).

But I was not satisfied with this solution... Mainly because it is basically quadratic in relation to Q, far from the expected time complexity.

My question is, has anyone ever solved this problem and knows a better algorithm? It does not need to be in Java, a pseudo-code or implementation in any language is ok.

Answer 1

I particularly believe that the best (or most reliable) solution is to apply autocorrelation, it is the same method used to find the period in signals, a very practical example of autocorrelation is when you need to find the frequency (which conversely is the same as the period) of a given audio signal the principle is very similar to that of the proposed problem, the autocorrelation can be defined as:

The steps to achieve the expected result is:

1. Apply autocorrelation to the bit vector.
2. The autocorrelation will return the most similar points.
3. Now with the vector returned by autocorrelation find all the peaks of this vector.
4. now that you know all the locations(peaks), subtract(find the difference) between the peaks.
5. Your period is the result of the first difference.

I did here quickly on Matlab to demonstrate the concept, follow some results of the presented by the problem:

---

vector = [1 1 1 0 1 1 1 0 1 1];

R = xcorr(vector);

[pks,locs]=findpeaks(R);

resultado=diff(locs);

resultado(1)

ans =

     4

---

vector = [1 0 1 0];

R = xcorr(vector);

[pks,locs]=findpeaks(R);

resultado=diff(locs);

resultado(1)

ans =

     2

---

vector =[1 0 0 1 1 1 0 0 1 1];

R = xcorr(vector);

[pks,locs]=findpeaks(R);

resultado=diff(locs);

resultado(1)

ans =

     5

Answer 2

At first I considered applying the algorithm of Detection of Floyd cycles, also known as the "turtle and rabbit" algorithm, but the problem seems to be simpler than that.

Logarithmic complexity features usually involve a comparison that decreases over time. For example, the binary search, which divides the vector always in two.

The fact that it is squared could also be associated with comparisons between the elements of the vector, as occurs with the bubble ordering algorithm (Bubble Sort).

All in all, plus the definition of the problem:

S[K] = S[K+P] for all K, where 0 K < Q P

I thought of a simple algorithm that works basically as follows:

1. Calculates the longest period by dividing the bit string size by 2, making P = T / 2, being T the bit string size.

2. Calculates the number of strings to compare by Q = LEN / P, always rounding up

3. For each K = 1..P and J = 2..K, compares each element in position K with the correspondent in position K * J + P, only when K * J + P <= T

   If you find a different element

   • If P > 1, decreases the period P and returns to the step 2 again
   • Otherwise, just keep going 4

4. If P <= 0 returns -1, else, return P

Practical example

Given the example number 955, whose binary value is 1110111011, we can calculate the initial values of Steps 1 and 2 as follows:

T = 10
P = 10 / 2 = 5
Q = 10 / 5 = 2

Then the comparison in Step 3 occurs as follows:

K = 1: 1 1 1 0 1 | 1 1 0 1 1 (equal)

K = 2: 1 1 1 0 1 | 1 1 0 1 1 (equal)

K = 3: 1 1 1 0 1 | 1 1 0 1 1 (different)

When comparing the third element of each period, a different element was found. Then, updated the variables like this:

P = P - 1 = 4
Q = 10 / 3 = 4 (arredondando para cima)

And we continue the comparison:

K = 1: 1 1 1 0 | 1 1 1 0 | 1 1 (equal)

K = 2: 1 1 1 0 | 1 1 1 0 | 1 1 (equals)

K = 3: 1 1 1 0 | 1 1 1 0 | 1 1 (equal)

K = 4: 1 1 1 0 | 1 1 1 0 | 1 1 (iguals)

As there is no difference, then we return the value of P, that is 4.

Java implementation

public static int periodo( int n ) {

  // validação inicial: precisa ser positivo e com pelo menos duas casas binárias
  if( n < 2 ) return -1;

  // inicialização de variáveis
  String s = Integer.toBinaryString( n );
  byte[ ] bytes = s.getBytes();
  int t = bytes.length;

  // período inicial
  int p = t / 2;

  // verifica se o período se repete pelo menos uma vez
  boolean diferente;
  do {
    diferente = false;
    int qp = t / p; // quantidade de períodos
    if (t % p > 0) qp++; //somar 1 para comparar os caracteres de resto no final

    // verifica se a repetição ocorre
    for2: for( int k = 0 ; k < p ; k++ ) {
      for (int j = 1; j < qp; j++) {
        if( k + p * j < t && bytes[ k ] != bytes[ k + p * j ] ) {
          diferente = true;
          break for2;
        }
      }
    }

    //se não encontrou repetição, tenta um período menor
    if( diferente ) {
      p--;
    }
  } while( diferente && p > 0 );

  return p <= 0 ? -1 : p;
}

Some Considerations

I’m not very good at judging the complexity of an algorithm, but I believe in the worst case the above algorithm will do N / 2 iterations and, in each, it makes iterations in shorter periods, which leads to a logarithmic temporal complexity.

As for the special (memory) complexity, the algorithm is O(1) because it does not add new data structures beyond the original, although the implementation is O(N) because it creates an auxiliary vector of the same bit string size.

Something that leaves me with a flea behind the ear is that the problem suggested a special complexity also logarithmic, so maybe there is some data structure that can optimize the temporal complexity of the solution.

One solution I thought of with logarithmic time complexity is to split the bit string into several strings and then compare to see if they have the same content. However, I suspect that this solution would be much less efficient, since it would execute several substrings seems to me something unnecessary, besides which the comparison of Strings would also occur character to character.

Another idea is to recover the binary section of each period and compare the equivalent in its numerical format. Perhaps still with binary operations the algorithm could be very efficient. But I haven’t analyzed the complexity of converting each period from binary to decimal format.

Yet another idea to optimize this further would be to make all this comparison using binary operators to check the equality of periods, for example, using bit chains like this: 1000010000, 1000100010, 1001001001, 1010101010. It’s an idea.

Finally, I do not know if the solution I proposed meets the requirement of the question, but I hope to have helped at least with some ideas.

And, before concluding, just one warning: beware of language performance when participating in an online challenge. I have already solved some of these problems using Java and Python. Unfortunately, I often got one timeout even with a good algorithm. Some sites add speed multipliers, for example Java 1,5 and Python 2,5 to try to match the efficiency of the algorithm with faster languages like C++. However, this is not always fair and just look at the ranking to see which languages are always at the top.

---

Updating

Based on gist from Anthony Accioly, I made an attempt to further optimize code using bit-only manipulation. Follow the code:

public class BitPeriod5 {

    public int solution(int n) {

        // validação inicial: precisa ser positivo e com pelo menos duas casas binárias
        if (n < 2) {
            return -1;
        }

        // inicialização de variáveis
        final int t = 32 - Integer.numberOfLeadingZeros(n);

        // descarta bits não significantes
        final int s = n >>> Integer.numberOfTrailingZeros(n);

        // período inicial
        int p = 1;
        int maxp = t / 2;
        int vp = 0;

        // verifica se o período se repete pelo menos uma vez
        boolean diferente;
        do {
            diferente = false;
            int qp = t / p + 1;
            if (t != p * qp) {
                qp++; //somar 1 para comparar os caracteres de resto no final
            }

            vp = vp << 1 | 1;
            int vi = n & vp;
            for (int i = 1; i < qp; i++) {
                if (((n >> (i*p)) & vp) != (vi & vp)) {
                    diferente = true;
                }
            }

             //se não encontrou repetição, tenta um período menor
            if (diferente) {
                p++;
            }
        } while (diferente && p <= maxp);

        return p > maxp ? -1 : p;

    }

    public static void main(String[] args) {
        final BitPeriod5 bitPeriod = new BitPeriod5();
        for (int i = 0; i < 100; i++) {
            long nano = System.nanoTime();
            for (int j = 0; j < 100000; j++) {
                bitPeriod.solution(10);
                bitPeriod.solution(187);
                bitPeriod.solution(955);
                bitPeriod.solution(1000000000);
                bitPeriod.solution(0b10101000001010100000);
            }
            System.out.printf("%.2f\n", ((double) (System.nanoTime()) - nano) * 1e-6);
        }
    }

}

However, I noticed that this solution is slower than the previous one, even though it has a for unless.

Lesson 1

Manipulating bits is more "expensive" than accessing vector elements and comparing their value.

I also noticed that removing the module operation, the performance of the code greatly improves.

Changing the section:

if (t % qp > 0) ...

That’s why:

if (t != p * qp) ...

The performance gain was in the 25% range. It is very interesting to see how each operation most drastically affects the performance.

Lesson 2

The division module operation is very "expensive" from the performance point of view.

Answer 3

A week after the "30 minutes exercise" I finally managed to reach a solution using bit manipulation.

This algorithm continues to be brute force; but it achieved the best times as my tests (on average 6 times faster than the original algorithm).

The algorithm

1. For every candidate for a term P amid 1 and Q / 2
   2. Boot K: P top order bits in N.
   3. Find S: a chain of Q bits using successive repetitions of K ("remains" should be considered).
   4. If S == N, the period is P
2. If no period was found, returns -1.

Implementation

public int periodo(int n) {
    if (n <= 0) {
        throw new IllegalArgumentException("n precisa ser positivo");
    }
    int result = - 1;
    // tamanho da cadeia de bits
    final int q = 32 - Integer.numberOfLeadingZeros(n);
    // cada periodo entre p 1 e tamanho da cadeia / 2
    for (int p = 1; p <= q / 2 && result == -1; p++) {
        // primeiros p bits
        final int k = n >> q - p;
        if (n == constroiPeriodo(k, p, q)) {
            result = p;
        }
    }
    return result;
}

Where the method constroiPeriodo can be implemented as follows:

private int constroiPeriodo(int k, int p, int q) {
    int result = 0;
    // periodos inteiros
    for (int i = 0; i < q; i += p) {
        result = result << p | k;
    }
    // ultimo periodo parcial
    final int mod = q % p;
    if (mod != 0) {
        result = result >> p - mod;
    }

    return result;
}

---

P.S. While my adaptation of utluiz algorithm failed to achieve the performance of that implementation naive, his algorithm is much smarter and should be preferred.