Codility Binary Period

Question

This is a problem Codility exam, I think there must be a more efficient way to do it. (And also I know there is a way to convert Binary number directly without going through the BinaryString, but I dont know how).

This is the problem:

A non-empty zero-indexed string S consisting of Q characters is given. The period of this string is the smallest positive integer P such that:

P ≤ Q / 2 and S[K] = S[K+P] for 0 ≤ K < Q − P.

For example, 8 is the period of "codilitycodilityco". A positive integer M is the binary period of a positive integer N if M is the period of the binary representation of N.

For example, 4 is the binary period of 955, because the binary representation of 955 is "1110111011" and its period is 4. On the other hand, 102 does not have a binary period, because its binary representation is "1100110" and it does not have a period.

Write a function:

int solution(int N);

that, given a positive integer N, returns the binary period of N. The function should return −1 if N does not have a binary period.

For example, given N = 955 the function should return 4, and given N = 102 the function should return −1, as explained in the example above.

Assume that:

N is an integer within the range [1..1,000,000,000].

Complexity:

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

• expected worst-case space complexity is O(log(N)).

  public class SecondTask { public int solution(int N) { String binario = Integer.toBinaryString(N);

        int minimo = Integer.MAX_VALUE;
        int Q = binario.length();
  
        for(int P=1;P<Q;P++)
        {
            float der =Q/2;
            if(P<=der)
            {
                int delta = Q-P;
                int fail=0;
                for(int K=0;K<delta;K++)
                {
                    if(binario.charAt(K)!=binario.charAt(K+P))
                    {
                        K=delta;
                        fail=1;
                    }
                }
                if(fail!=1)
                {
                    if(P<minimo)
                    {
                        minimo=P;
                    }
                }
            }
        }
        if(minimo==Integer.MAX_VALUE)
        {
            return -1;
        }
        return minimo;
    }    
  

  }

Probably the code is extremely inefficient but as we go I'll be fixing it. Should be something simple :-(.

Edit: after @Eran's help, this is the new code. The running time is practically the same but its clean now.

public class SecondTask {
    public int solution(int N) 
    {
        String binario = Integer.toBinaryString(N);
        
        int minimo = Integer.MAX_VALUE;
        int Q = binario.length();
        System.out.println("binario: "+binario);
        for(int P=1;P<Q/2;P++)
        {
            System.out.print("P: "+P);
            int delta = Q-P;
            int fail=0;
            for(int K=0;K<delta;K++)
            {
                System.out.print(" "+binario.charAt(K));                
                if(binario.charAt(K)!=binario.charAt(K+P))
                {

                    K=delta;
                    fail=1;
                }
            }
            System.out.println("");
            if(fail!=1)
            {
                return P;
            }
        }
        
        if(minimo==Integer.MAX_VALUE)
        {
            return -1;
        }
        return minimo;
    }    
}

Answer 1

Your implementation is not ideal.

For example, instead of

for(int P=1;P<Q;P++)
{
    float der =Q/2;
    if(P<=der)

you can write

for(int P=1;P<=Q/2;P++)
{

That could save you a few iterations that do nothing.

Another change I would do is replace :

        if(fail!=1)
        {
            if(P<minimo)
            {
                minimo=P;
            }
        }

with :

        if(fail!=1)
        {
           return P;
        }

since once you find a P that is a valid period, you can stop searching.

However, these improvements wouldn't change the time complexity, and your implementation already meets the complexity requirements.

A number N is represented by O(log(N)) bits, so Q = O(log(N)).

Your implementation has a loop within a loop, and the size of each loop is smaller than Q. Therefore the worst case time complexity is bound by Q^2, which is O(log(N)^2), which is the required complexity.

The space complexity of O(log(N)) is also met, since the only non-constant length storage you use is that of the binary string representation of N (the binario variable), whose length is O(log(N)).

I'm not sure whether there's an implementation with a better time complexity.