Day 10: HackerRank 30 Days Of Code Solution | Binary Numbers

Day 10 of HackerRank's 30 Days of Code is about binary numbers. You take a normal decimal number, look at its binary form, and find the longest unbroken run of 1s. It checks two things: whether you know how to pull out the bits of a number one by one, and whether you can track a "current streak versus best streak" while looping, which is a pattern you will use in many array problems too.

Binary also comes up often in interviews (bit tricks, powers of two, set bits), so it is worth solving this in a way you fully understand rather than copying a one-liner.

Problem

You are given a positive integer n in base 10. Write it in base 2 and print the length of the longest sequence of consecutive 1s in that binary form, as a normal base-10 number.

Input: one integer n.

Output: one integer, the maximum number of consecutive 1s in the binary representation of n.

Constraints: 1 ≤ n ≤ 10⁶.

Input:
13

Output:
2

13 in binary is 1101. The runs of 1s are "11" and "1", so the longest is 2. A second sample on HackerRank is 5, which is 101 in binary, giving 1.

Approach

How do you read the bits of a number without converting it to a string? Use the same method you learned in school for converting to binary: divide by 2 again and again. Each remainder is the next bit, starting from the rightmost one.

• n % 2 gives the last bit (1 if n is odd, 0 if even).
• n / 2 (integer division) removes that last bit.

While reading bits, keep two counters:

1. current: how many 1s in a row you have just seen.
2. best: the longest run seen so far.

When the bit is 1, increase current and update best if needed. When the bit is 0, the run is broken, so reset current to 0. Stop when n becomes 0.

Reading the bits from right to left is fine, because a run of 1s is the same length whichever direction you read it in.

Dry run with n = 13:

• 13 % 2 = 1, current = 1, best = 1, n becomes 6.
• 6 % 2 = 0, current = 0, n becomes 3.
• 3 % 2 = 1, current = 1, best stays 1, n becomes 1.
• 1 % 2 = 1, current = 2, best = 2, n becomes 0. Stop.

The answer is 2.

Solution in Java

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();

        int current = 0;  // length of the run of 1s we are inside right now
        int best = 0;     // longest run seen so far

        // Read the bits from right to left using % 2 and / 2
        while (n > 0) {
            if (n % 2 == 1) {
                current++;
                best = Math.max(best, current);
            } else {
                current = 0;   // a 0 breaks the run
            }
            n = n / 2;
        }
        System.out.println(best);
    }
}

The old solution on this page used a well-known bit trick: repeat n = n & (n << 1) and count how many times you can do it before n becomes 0. Each step shortens every run of 1s by one, so the number of steps equals the longest run. It is correct and clever, but hard to explain if you have not seen it before. The loop above is what I would write first in an interview, and then mention the trick as an option.

You could also use Integer.toBinaryString(n) and scan the characters, or split it on "0" and take the longest piece. Those work too but create extra strings.

Tests I ran:

• 5 gives 1 (binary 101).
• 13 gives 2 (binary 1101).
• 1 gives 1, the smallest input.
• 6 gives 2 (binary 110). The run is at the left end, so the answer is only found on the last loop step, which checks that we update best inside the loop.
• 1000000 gives 4 (binary 11110100001001000000).
• 524287 gives 19. It is 2¹⁹ - 1, which is nineteen 1s, the longest run possible within the limit.

Output

2

Complexity

Time: O(log n). The loop runs once per bit, and a number up to 10⁶ has at most 20 bits.

Space: O(1). Just two counters. The toBinaryString approach would need O(log n) extra space for the string.

Common mistakes

• Updating best only when you hit a 0. If the number ends with its longest run (like 6 or 7), you never see a 0 after it and you print the wrong answer.
• Counting all 1s in the number instead of consecutive ones. 13 has three 1s but the answer is 2.
• Using n >> 1 and n & 1 is fine and a bit faster, but be careful with negative numbers in other problems, where >>> is needed. Here n is always positive.
• Printing the binary string itself instead of the count.

Next in the series: Day 11: 2D Arrays. For more practice with number systems, try the Number Systems and Binary Codes MCQs.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More HackerRank solutions All coding problems MCQ practice