3
\$\begingroup\$

I have picked up a problem from Codility website and tried to work it out.

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

Write a function:

class Solution { public int solution(int N); }

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

I would appreciate guidance of how to refactor it and what to look for in terms of efficiency?

Optimisation I'd like to achieve would be, less type conversion, no zero items in the list, would there be a better way to find the max number in a list, or .Sort(); is good enough?

Any ideas welcome, thank you.

using System;
using System.Collections.Generic;

namespace rec
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            Console.WriteLine(FindGap(777)); // 
        }

        public static int FindGap(int number)
        {
            string toBinary = Convert.ToString(number, 2);

            char[] toChar = toBinary.ToCharArray();

            string previous = "";
            string current = "";
            int count = 0;
            int answer = 0;
            List<int> lastGap = new List<int>();

            for (int i = 0; i < toChar.Length; i++)
            {
                if (toChar[i].ToString() == "1")
                {
                    // temp becomes 1
                    current = toChar[i].ToString();

                    if (current == "1")
                    {
                        lastGap.Add(count);
                        count = 0;
                        continue;
                    }
                }
                if (toChar[i].ToString() == "0" && current == "1")
                {
                    current = "0";

                    count++;

                    previous = current;
                }
                else if (toChar[i].ToString() == "0" && previous == "0")
                {
                    current = "0";
                    count++;
                    previous = current;
                }
            }
            lastGap.Sort();
            answer = lastGap.Last();

            if (answer > 1)
            {
                return answer;
            }
            else return 0;
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! Please provide a (possibly abbreviated) challenge description with your code review request. There may be subtleties not covered by the short description in the question title. \$\endgroup\$ – AlexV May 23 '19 at 20:44
  • \$\begingroup\$ @t3chb0t You have changed the question to mention only positive numbers. This makes my answer completely irrelevant :-) \$\endgroup\$ – dfhwze May 24 '19 at 6:08
  • \$\begingroup\$ @dfhwze are you sure you mean me? I've just added one tag. Mhmm.... I don't usually edit programming-challenges as I'm not a fan ;-] \$\endgroup\$ – t3chb0t May 24 '19 at 6:09
  • 1
    \$\begingroup\$ Welcome to Code Review. I have rolled back your last edit. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Heslacher May 24 '19 at 10:52
  • 1
    \$\begingroup\$ Just read the provided link to know what you are allowed to do. \$\endgroup\$ – Heslacher May 24 '19 at 12:35
4
\$\begingroup\$

If you're just looking for the longest stretch of zeros you don't need to use a list at all. You just iterate through the binary representation until you find a stretch of zeros. If you hit a new high score, you can overwrite the old high score with the new one and keep moving forward, forgetting about the past.

This is called a "greedy algorithm."

    public static int FindGap(int number)
    {
        string binaryRep = Convert.ToString(number, 2);

        int maxGapSize = 0;
        int currGapSize = 0;

        foreach(char ch in binaryRep)
        {
            if (ch == '0')
            {
                currGapSize++;
            }
            else
            {
                maxGapSize = Math.Max(currGapSize, maxGapSize);
                currGapSize = 0;
            }
        }

        return maxGapSize;
    }

If you want to get really fancy, you don't even need to convert the number to a string. You can use bit shifts to "iterate" through the bits in the number. The number 9 is 1001 in binary. Shift the bits over one, and you've got 100. Shift it over again, and you've got 10. You can use modulus operations to see if the least significant digit is 0 or 1.

This is just a fancy way to repeatedly divide by 2. In fact, you could solve this problem by dividing by 2 instead but this way works as well. (There's also probably a more terse way to write this, but this is perfectly efficient.)

    public static int FindGap2(int number)
    {
        int maxGapSize = 0;
        int currGapSize = 0;

        if (number == 0)
            return 0;

        while (number % 2 == 0)
            number = number >> 1;

        while (number > 0)
        {
            if(number%2 == 0)
            {
                currGapSize++;
            }
            else
            {
                maxGapSize = Math.Max(currGapSize, maxGapSize);
                currGapSize = 0;
            }
            number = number >> 1;
        }

        return maxGapSize;
    }
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I was answering this way (the chars alternative) then i thought: this is reinventing the wheel, and now your comment "this is called a grredy algorithm" made me think: maybe that website is doing an introduction to regex ! Probably this is what they wanted . \$\endgroup\$ – L.Trabacchin May 23 '19 at 22:45
  • 1
    \$\begingroup\$ @slothario is for some reason you could not access Math.Max you could just write your own: int32 Max(int32 a, int32 b) => a > b ? a : b; one line :) \$\endgroup\$ – L.Trabacchin May 24 '19 at 10:18
  • 1
    \$\begingroup\$ @L.Trabacchin You can check my answer below to see it does not work for negative integers. The solution with a guard is a safe one, no doubt. But I understood that the problem was to find the gaps on any Int32. In this case, negative numbers had to be transformed first to UInt32. \$\endgroup\$ – dfhwze May 24 '19 at 10:40
  • 1
    \$\begingroup\$ @Kris You don't need Math.Max(). You can use the inline solution L.Trabacchin mentioned, or even a simple if statement. I.e., if(currGapSize > maxGapSize) currGapSize = maxGapSize. I prefer Math.Max just for style reasons, but either case is totally fine. If you want to get really good at this style of problem, I encourage you to take a brief tutorial on bit operations and remember things like Math.Max! It will make you a stronger coder and interviewer. \$\endgroup\$ – Slothario May 24 '19 at 22:02
  • 1
    \$\begingroup\$ Indeed, Math.Max is definitely part of my arsenal now thanks to you, thanks for the support @Slothario \$\endgroup\$ – Kris May 25 '19 at 14:02
2
\$\begingroup\$

There is no need to convert the integer into a string. That's too expensive in terms of CPU usage and memory consumption.

As I answered in a Java question on the same topic a few days ago, there's a simple solution using only integer arithmetics. That solution can be easily translated into C#.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

I think that part of the exercise is to make you re-invent the wheel just to learn that documentation is your friend, discovering something you just did already existed, in your case you really wrote everything also the Math.Max.

Part to become a good programmer is find a way to make your code reusable, so one BIG advice is refactor your code in a way that small functionality can be reused, in fact you could write your own separate function to do that.

Class Math 
{
    static Int32 Max(Int32 a, Int32 b) => a > b ? a : b;
}

But as i said an even bigger part of becoming a good programmer is learn to read the documentation, and avoid reinventing the wheel, because the wheel must be mantained, and could become hard. Framework doc

So, what about considering System.Text.RegularExpressions ?

Amazing resource to learn all the superpowers they come with

If i understood right 000000010000100000 should return 4, the initial bytes and the end ones are not took in account since they are not surrounded by ones.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace ConsoleApp
{
    class Program
    {
        static void Main(String[] args)
        {
            for (var i = 0u; i <= 5000u; i++)
            {
                var binaryRepresentation = Convert.ToString(i, 2);
                Console.WriteLine($"{i} => {binaryRepresentation} : {GetLongestAmountOfConsecutiveZeros(binaryRepresentation)}");
            }
            Console.ReadKey();
        }

        static readonly Regex BinaryGapRegex = new Regex("1(0+)1", RegexOptions.CultureInvariant);
        private static Byte GetLongestAmountOfConsecutiveZeros(String bits)
        {
            var matches = BinaryGapRegex.Matches(bits).Cast<Match>();
            var successingMatches = matches.Where(x => x.Success);
            var successingMatchesWithGroup = successingMatches.Where(x => x.Groups[1].Success /* Group 0 is the whole match with also the ones, group one is just the brackets part*/);
            var eachGroupLength = successingMatchesWithGroup.Select(x => /* Will never be longet than 32 */ (Byte)x.Groups[1].Value.Length);
            var longestGroup = !eachGroupLength.Any() ? Byte.MinValue : eachGroupLength.Max();
            return longestGroup;
        }
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Since this is Code Review where we review code and provide suggestions on how to improve the code can you make some observations about the Posters code? Your answer might be very good on stack overflow but it isn't really meeting the goals of code review. Please see codereview.stackexchange.com/help/how-to-answer. \$\endgroup\$ – pacmaninbw May 24 '19 at 1:13
  • 1
    \$\begingroup\$ sorry i come exactly from stackoverflow... Could I say that the poster code is very long and complicated while this can be achieved in a easier shorter way using a different approach? \$\endgroup\$ – L.Trabacchin May 24 '19 at 10:16
  • \$\begingroup\$ That would be a start in the correct direction. \$\endgroup\$ – pacmaninbw May 24 '19 at 10:20
  • 1
    \$\begingroup\$ Thanks big L. note taken! \$\endgroup\$ – Kris May 25 '19 at 14:01
2
\$\begingroup\$

Review

The initial question did not state it had to work only for positive integers. But after an edit, it does, rendering my answer mute. Anyway, I leave my answer up for those how are interested in an altered solution to work for all integers, regardless of sign.

public static void Main()     
{
    // 11111111111111111111111111110011
    Console.WriteLine(Convert.ToString(-13, 2)); 
    // 0 -> incorrect         
    Console.WriteLine(FindGap(-13));  
}

After proposed fix:

public static void Main()   
{
    // 11111111111111111111111111110011
    Console.WriteLine(Convert.ToString(-13, 2)); 
    // 2 -> correct
    Console.WriteLine(FindGap(-13));    
}

FindGaps with binary arithmetic works also for strict negative numbers if we first translate the int to uint.

public static int FindGap(int number)
    {
        ..

        if (number == 0)
            return 0;

        ..
    }
public static int FindGap(int number)
    {
        ..
        //var n = BitConverter.ToUInt32(BitConverter.GetBytes(number), 0);
        var n = unchecked((uint)number); // even better approach

        if (n == 0)
            return 0;
       ..
    }

Proposed Solution

public static int FindGap(int number)
    {
        int maxGapSize = 0;
        int currGapSize = 0;
        var n = unchecked((uint)number);

        if (n == 0)
            return 0;

        while (n % 2 == 0)
            n = n >> 1;

        while (n > 0)
        {
            if(n%2 == 0)
            {
                currGapSize++;
            }
            else
            {
                maxGapSize = Math.Max(currGapSize, maxGapSize);
                currGapSize = 0;
            }
            n = n >> 1;
        }

        return maxGapSize;
    }

Remarks

Int32 storage in C#:

In addition to working with individual integers as decimal values, you may want to perform bitwise operations with integer values, or work with the binary or hexadecimal representations of integer values. Int32 values are represented in 31 bits, with the thirty-second bit used as a sign bit. Positive values are represented by using sign-and-magnitude representation. Negative values are in two's complement representation. This is important to keep in mind when you perform bitwise operations on Int32 values or when you work with individual bits. In order to perform a numeric, Boolean, or comparison operation on any two non-decimal values, both values must use the same representation.

About bit-shifting in C#

  • If the first operand is of type int or long, the right-shift operator performs an arithmetic shift: the value of the most significant bit (the sign bit) of the first operand is propagated to the high-order empty bit positions. That is, the high-order empty bit positions are set to zero if the first operand is non-negative and set to one if it's negative.
  • If the first operand is of type uint or ulong, the right-shift operator performs a logical shift: the high-order empty bit positions are always set to zero.

This means that -1 is represented as 11111111111111111111111111111111. If we would allow >> on this value, we would get the value back, causing an infinite loop in your flow at n = n >> 1;. By converting the storage of the bytes from int to uint (is not the same as casting), we can perform all bit operations as expected. Hence, var n = unchecked((uint)number);.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I would then proceed to explain why it does not work with negative numbers, and how they are represented, so he can understand why converting them to Strings is not the same as they are in memory \$\endgroup\$ – L.Trabacchin May 24 '19 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.