bug code

leo2008 (147)

Below code gives some bugs some inputs which seems to be incorrect, which I am trying to figure out, there focus on correctness of the code rather than performance here.

Here my function int solve(int n), this function when given a positive integer n, return binary period of n. The function return -1 if n does not have a binary period.

I assume that the n integer ranger is [1..1,000,000,000].

    int solve(int n) {
    int e[30];
    int l = 0;
    while (n > 0) {
        e[l] = n % 2;
        n /= 2;
        l++; 
    }
    for (int p = 1; p < 1 + l; ++p) {
        bool ok = true;
        for (int i = 0; i < l - p; ++i) {
            if (e[i] != e[i + p]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            return p;
        }
    }
    return -1;
}

Last edited on

keskiverto (10402)

gives some bugs some inputs which seems to be incorrect

There is "some answer"?

Give at least one example input, what you expect to get as output (and why), and what you actually get.

salem c (3700)

More palming off someone else's work as your own.
https://codereview.stackexchange.com/questions/197807/c-code-to-calculate-the-binary-period-of-an-integer

leo2008 (147)

The link that you pointed out here is C code. Is converting integer to binary proper here?

An example would be 955 which will have a binary period 4. For 955, the binary value is 1110111011 and hence period is 4.

jonnin (11437)

what is 'the answer' for 1111111111111111 ...
this looks like something that would be easier and more efficient to do in reverse.
there are only a few binary combinations that are valid. assemble them, extract the integers and period from those, and everything else is -1
not sure why you limit the input. may as well use all the bits, its easier, but even so the above you can throw away values > range.
note that when you find a valid combination, its ~ is also valid, so you only have to find half of them. that is, if 100100100 is valid then 011011011 is also valid (binary not)
basically all zeros, all ones, then every combination of 2 bits repeated, every combination of 3 bits repeated, ... its a lot of combinations for 32 bits (all 16 bit values repeated twice) but once you have the data one time, its just a hard coded lookup table to make the real solver.
**you do realize they repeat, also? Every combination of 2 bits repeated, well, 00 and 11 are just repeating the all ones and all zeros. Every combination of 3 bits, not only will 000 and 111 repeat like the 2 bits but some of them will overlap the 2 bit patterns as well. If you extrapolate that, you can skip a LOT of work as you add bits, and its probably some trick to it like only need to generate the prime bitcounts like 2,3,5,7,11,... since 9 is going to mirror all the 3 bit patterns, and the even ones will mirror the 2 bit patterns, ... right?

Last edited on

keskiverto (10402)

The link that you pointed out here is C code. Is converting integer to binary proper here?

That linked question also says: "The Challenge states that by modifying at most 2 lines"
In other words, the code is wrong on purpose. You have to understand what it does and how to change it to get the correct result.

What do you get with that example, 955?

leo2008 (147)

I had considered here a non empty string A = A[0] A[1]...A[T-1] consisting of T characters.
Here the string period is considered the smallest positive integer I provided:
I <= T/2 and A[L] = A[L+I] for every L, where 0 <= L < T - I.

For example 955 in binary is 1110111011 and its period is 4.
Ideally the function int solve (int n) implementation when given a positive integer "n", returns binary period of "n", else that function returns -1 (if "n" do not have binary period).

Last edited on

lastchance (6980)

#include <iostream>
#include <string>
using namespace std;

string binary( int n ) { return ( n > 1 ? binary( n / 2 ) : "" ) + "01"[n%2]; }

bool periodic( const string &str, const string& s )
{
   int p = s.size();
   if ( str.size() >= p ) return str.substr( 0, p ) == s && periodic( str.substr( p ), s );
   else                   return str == s.substr( 0, str.size() );
}

int period( int n )
{
   string bin = binary( n );
   for ( int p = 1; p <= bin.size() / 2; p++ ) if ( periodic( bin.substr( p ), bin.substr( 0, p ) ) ) return p;
   return -1;
}

int main()
{
   for ( int i : { 955, 1651, 102, 54 } ) cout << i << " : " << binary( i ) << " : " << period( i ) << '\n';
}

955 : 1110111011 : 4
1651 : 11001110011 : 5
102 : 1100110 : -1
54 : 110110 : 3

#include <iostream>
#include <string>
using namespace std;

string binary( int n ) { return ( n > 1 ? binary( n / 2 ) : "" ) + "01"[n%2]; }

string operator *( int n, const string &str ) { return n ? str + ( n - 1 ) * str : ""; }

int period( int n )
{
   string bin = binary( n );
   for ( int p = 1; p <= bin.size() / 2; p++ )
   {
      string repeat = bin.substr( 0, p );
      int times = bin.size() / p;
      string leftover = repeat.substr( 0, bin.size() % ( p * times ) );
      if ( bin == times * repeat + leftover ) return p;
   }
   return -1;
}

int main()
{
   for ( int i : { 955, 1651, 102, 54 } ) cout << i << " : " << binary( i ) << " : " << period( i ) << '\n';
}

#include <iostream>
#include <string>
using namespace std;

string binary( int n ) { return ( n > 1 ? binary( n / 2 ) : "" ) + "01"[n%2] ; }

int period( int n )
{
   string bin = binary( n );
   for ( int p = 1; p <= bin.size() / 2; p++ )   // must have at least 2 complete periods
   {
      bool ok = true;
      for ( int i = p; i < bin.size(); i++ )
      {
         if ( bin[i] != bin[i-p] )
         {
            ok = false;
            break;
         }
      }
      if ( ok ) return p;
   }
   return -1;
}

int main()
{
   for ( int i : { 955, 1651, 102, 54 } ) cout << i << " : " << binary( i ) << " : " << period( i ) << '\n';
}

Last edited on

leo2008 (147)

Thanks a lot lastchance, I am studying your code, it helps a lot.

Topic archived. No new replies allowed.