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
Initialize a counter variable to zero.
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.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.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;
}