Conversion to binary Number

funkey_monkey

Hi,

I'm currently doing the HackerRank 30 day challenge and today it was on Binary numbers. The topic itself was not difficult, but I did struggle a bit with the programming question:

Objective
Today, we're working with binary numbers. Check out the Tutorial tab for learning materials and an instructional video!

Task
Given a base-10 integer, n, convert it to binary (base-2). Then find and print the base-10 integer denoting the maximum number of consecutive 1's in n's binary representation.

Input Format
A single integer, n.

Constraints
1 <= n <= 10^6

Output Format
Print a single base-10 integer denoting the maximum number of consecutive 1's in the binary representation of n.

Sample Case 1:
The binary representation of 5 is 101, so the maximum number of consecutive 's is 1.

Sample Case 2:
The binary representation of 13 is 1101, so the maximum number of consecutive 's is 2.

My first thought in design here was to convert n from an integer into a binary representation using an inbuilt C++ library function. I would then convert the number to a string and then parse over it character by character. However, I was unable to find such a function, so I had to change plan.

I then realised from re-reading the problem that the solution did not require to know the binary number - only the number of consecutive 1's.
I've got a bit of a problem with their definition of consecutive 1's as for me 101 has no consecutive 1's and 1101 only has a single consecutive 1 - as to me the first one doesn't count.

So, what I decided to do was to divide into n and determine the dividend and from this keep a rolling 2 deep buffer of the modulus of these divisions. By monitoring the buffer I could tally the number of consecutive 1's.
The fly in the ointment turned out to be how to determine if there were 1's which were not consecutive as these counted too. What I done here was (am I'm not sure if this is good coding practice in C++) that I set a Boolean equal to the integer n and if the Boolean equated to true (non-zero) then I added to the tally. This covered both the 1's in 101 and the first 'consecutive' 1 in the sequence in 1101.

My code works against all their test cases. So whats the problem? Well, I'd like to know how you would have approached this problem to see if my thought process was on the right lines.

What I don't like about my solution is that there are a number of conditional statements and a loop as well as six local variables - it just smells wrong and that there is a more efficient solution available. Although, I don't like sacrificing readability/maintainability for overly succinct/obscure/complex implementations.

Any advice appreciated:

#include <bits/stdc++.h>

using namespace std;


int determineConsequtiveOnes(int dividend){

    int quotient;
    int modulus[2] = {0};
    int index = 0;
    int consecutiveOnes = 0;
    int runningTally = 0;
    bool bitSet = dividend;

    do{
       quotient = dividend / 2;
       modulus[index] = dividend - (quotient * 2);

       // Check for consecutive ones
       if ((modulus[0] == 1) & (modulus[1] == 1)) {
          runningTally += 1;

          // Update maximum
          if (runningTally > consecutiveOnes){
             consecutiveOnes = runningTally;
          }
       }
       else
       {
          runningTally = 0;  // 0 encountered - reset the tally
       }
       
       index = (index + 1) % 2;  // Mod 2 counter
       dividend = quotient;  // Update the dividend for next calc

    }while(quotient > 0);

    if (bitSet == true){consecutiveOnes += 1;}
    
    return consecutiveOnes;
}

int main()
{
    int n;
    cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    cout << determineConsequtiveOnes(n);

    return 0;
}

Colonel Panic

You could use bitshifting and a mask to tally the number of consecutive 1s instead of what you're doing.

Remember, the integer you're doing all that work on is just 32 bits of data underneath.

14ned

My first guess would be a loop of bit rotation and bit scanning to find the first set bit. Both are single cycle CPU ops. If you write it correctly, the CPU can do four of those in parallel too.

But the classical answer would be bit twiddling, so there will be a combination of bit operations which solves the problem in constant time.

Search for "Hacker's Delight", lots of stuff in there for solving these sorts of problem.

Niall

funkey_monkey

Would I get laughed out of an interview if I presented that as a coding challenge solution?

Steve

This seems like a question of understanding basic logic. AND OR XOR, I'd look at it with that in mind.

Int -> binary array. Parse binary array using AND and an incremental counter.

14ned

funkey_monkey wrote: »

Would I get laughed out of an interview if I presented that as a coding challenge solution?

If an interviewee ever answers a problem with "the correct answer is probably on Hacker's Delight", they've probably just passed the technical stage as far as I'd be concerned.

The mark of experience is knowing how to quickly find an optimal answer, not knowing an answer. It's like sure, it would be great if a candidate had memorised the entire of Knuth, but the kind of person who would memorise Knuth will probably fail all or most of the non-technical parts of an interview such as fit and soft skills.

Hiring often involves judging fit with your team and potential growth rather than pure technical merit. I'd choose someone with poor technical skills but a naturally built in self improving work ethic anyday over a rock star engineer. The former will become an ever better engineer over time with very little effort, whereas the latter tends to leave within a year.

Niall

Tar.Aldarion

Is c++ a preference or you have to use it? In python you'd just us bin(), then split() on 0's and print the largest.

Otherwise I'd use Colonel Panic's answer. In a for loop, bitshift the binary number, AND it with the original, this will remove a 1 from every sequence of 1's
When the number is eventually all 0's then the iteration count was the max amount of 1's in a sequence (break out of a while loop).

funkey_monkey

I'm using HackerRank to learn some C++.

14ned

funkey_monkey wrote: »

I'm using HackerRank to learn some C++.

https://doc.lagout.org/security/Hackers%20Delight.pdf says the fastest way of searching a population of bits for any one of a set of strings (in your case, 111111, 11111, 1111, 111, 11, 1) is De Bruijn cycles.

It does mention earlier that using the CPU opcodes for single cycle rotate and bit scan forward will be faster for those CPUs supporting those opcodes in single cycle forms.

Niall