From Decimal to Binary: A Journey to Finding the Maximum Consecutive Ones

Drawing inspiration from HackerRank's #30DaysOfCode Day 10 challenge on Binary Numbers, I present a comprehensive analysis of the problem and share my insights and techniques for successfully solving it.

Binary Numbers Challenge: See the Problem Here on HackerRank

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

Example

n = 125

The binary representation of 125 is 1111101. In base 10, there are 5 and 1 consecutive ones in two groups. Print the maximum, 5.

---

Algorithm

1. Initialize a counter variable to zero.

2. Convert the input integer to binary using the following steps:
   a. Initialize an array to store the binary digits.
   b. Divide the input integer by 2 and store the remainder in the array.
   c. Divide the input integer by 2 again and repeat step b until the input integer becomes zero.
   d. Reverse the array to get the binary representation.

3. Traverse the binary representation array and count the number of consecutive '1's.
   a. If the current element is 1, increment a counter variable.
   b. If the current element is 0, reset the counter variable to zero.
   c. If the counter variable is greater than the maximum number of consecutive '1's found so far, update the maximum.

4. Return the maximum number of consecutive '1's.

---

Solution

We will create a function called max_consecutive_ones that takes a decimal number as input and returns an integer. The purpose of this function is to count the number of consecutive ones in the binary representation of the input decimal number.

int max_consecutive_ones(int n) {
//code to convert decimal number to binary and count consecutive ones
}

Step 1:

To store the binary numbers, let's create an array named binary, int binary[32];

We need three more variables named i, max, and count and these are going to be initialized with zero.

int binary[32]; //to store array of binary numbers
int i = 0; //for indexing array
int max = 0; //to store the maximum number of ones
int count = 0; //to count the number of ones

Step 2:

Converting Decimal to Binary

In binary representation, each digit (or bit) can only take on the values 0 or 1. To convert a decimal number to binary, we repeatedly divide the decimal number by 2 and store the remainder at each step. The remainder will always be either 0 or 1, which corresponds to the binary digits 0 and 1, respectively.

Example: Converting 13 to its binary representation

13 / 2 = 6; //remainder 1
 6 / 2 = 3, //remainder 0
 3 / 2 = 1, //remainder 1
 1 / 2 = 0, //remainder 1

Reading the remainders from bottom to top, we get the binary representation of 13, which is 1101.

Based on this let's write code. I'm going to use while loop here.

The while loop repeatedly divides n by 2 and stores the remainder in the binary array until n becomes zero. At each iteration, the remainder (which is either 0 or 1) is stored in the binary array at the index i. Then, n is updated to be n/2 using n = n / 2. Finally, the index i is incremented by 1 to move to the next position in the binary array.

while (n > 0) {
    binary[i] = n % 2;
    n = n / 2; //or use shorthand n /= 2
    i++;
}

When the loop finishes executing, the binary array contains the binary representation of the decimal number n, with the least significant bit (i.e., the digit representing the units place in the binary number) stored at the first index of the array. To obtain the binary number in the correct order, the array needs to be read in reverse order.

Step 3:

To count the number of ones, we need to iterate through the array. For loop would be good in this case.

i contains the total number of elements in the array. We need to traverse the array in reverse order to get the correct result.

for(int j = i - 1; j >= 0; j--) {
//statements
}

Every time we encounter 1 during traversing we need to increment the count variable. At the same time check if countvariable becomes greater than max. If that happens, assign the value of count to max.

If we encounter 0, reset the count variable to zero.

for(int j = i - 1; j >= 0; j--) {
    if(binary[j] == 1) {
        count++;
        if(count > max){
            max = count;
        }
    }
    else {
        count = 0;
    }
}

Now all we have to do is return the max variable.

---

Complete Code

//function to convert number to binary and count consecutive ones
int max_consecutive_ones(int n) {
    int binary[32];
    int i = 0;
    int max = 0;
    int count = 0;

    //converting n to binary
    while (n > 0) {
        binary[i] = n % 2;
        n /= 2;
        i++;
    }

    //Traversing the array and count consecutive ones
    for(int j = i-1; j >= 0; j--) {
        if(binary[j] == 1) {
            count++;
            if(count > max) {
                max = count;
            }
        }
            else {
                count = 0;
            }
        }
    return max; 
}