Binary String Question to find maximum power of 2

Question

We have given a binary String of length n,we can cyclically shift this string any number of times.Let X be the decimal representation of string s. Find the greatest power of 2 with which X can be divisible with, if it can be divisible with arbitrarily large power print "-1".For the result, you are required to print a single integer denoting the maximum power of 2 by which X can be divisible with. ex: Input: 0011 Output: 2

Explanation:We can cyclically shift the string 2 times to get "1100" which is divisible by 2^2 hence the answer is 2.

Here is my solution .. however it is giving me tle on most of the test cases and wrong answer on some of the test cases..

int highestpower(int n)
{
    return (n & (~(n - 1)));
}

int findnum(string s)
{
    int value = 0;
    int p=0;
    for(int i = s.length()-1;i>=0;i--)
    {
        value = value+pow(2,p)*(s[i]-'0');
        p++;
    }
    return value;
}

int maximumPower(string s) {
    int ans = 0;
    for(int i=0;i<s.length();i++)
    {
        
        int num = findnum(s.substr(i)+s.substr(0,i));
        ans = max(ans,highestpower(num));
    }
    return ans/2;
}

how can I solve this answer?Thanks..

Answer 1

I have some difficulty to understand the logic of your code. In practice, it failed on about all cases I have tested.

Moreover, it seems quite over-complicated. It is enough to count the number of consecutive zeros. We just have to pay attention that this calculation must be performed in a cyclic way. For example, if s == 00100, the count number is 4, as after shifting, we get 10000. One simple way to handle this cyclicity is to concatenate the string s2 = s+s = 0010000100 and then to count the maximum number of consecutive zeros in the obtained string s2. In addition, we must pay attention that the input string is not composed of zeros only.

In the following code, I compared your code (maximumPower) with mine (maximumPower_new), on several different inputs.

Result:

0011    : 2  new: 2
0100010 : 4  new: 3
00100   : 8  new: 4

The code:

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

int highestpower(int n)
{
    return (n & (~(n - 1)));
}

int findnum(const std::string& s)
{
    int value = 0;
    int p=0;
    for(int i = s.length()-1;i>=0;i--)
    {
        value = value+pow(2,p)*(s[i]-'0');
        p++;
    }
    return value;
}

int maximumPower(const std::string& s) {
    int ans = 0;
    for(int i = 0; i < s.length(); i++)
    {
        int num = findnum(s.substr(i)+s.substr(0,i));
        ans = std::max(ans,highestpower(num));
    }
    return ans/2;
}

int maximumPower_new (const std::string& s) {
    int n = s.length();
    if (n == 0) return -1;
    std::string s2 = s + s;
    int count = 0;
    int count_max = 0;
    for (auto c: s2) {
        if (c == '0') {
            count ++;
        } else {
            count_max = std::max(count, count_max);
            count = 0;
        }
    }
    count_max = std::max(count, count_max);
    if (count_max >= n) return -1;
    else return count_max;
}

int main() {
    for (std::string s: {"0011", "0100010", "00100"}) {
        std::cout << s << " : " << maximumPower(s) << " new: " << maximumPower_new(s) << "\n";
    }
}