Binary Gap - Codibility - C#

BinaryGap.cs

using System;

namespace ObjectApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = new Solution();
            Console.WriteLine(S.solution(0));
        }
    }

    class Solution
    {
        public int solution(int n)
        {
            string bits = Convert.ToString(n, 2);
            //Console.WriteLine($"Bit String: {bits}");
            int longest = 0;
            int curCount = 0;

            for (int i = 0; i < bits.Length; i++)
            {
                if (bits[i] == '0')
                {
                    if (curCount > 0) curCount++;
                    else curCount = 1;
                } else curCount = 0;
                if (curCount > longest) longest = curCount;
            }

            return longest;
        }
    }
}

Here is a solution using a binary mask, twice the efficiency. On 400,000 runs completes in 36 milliseconds compared to 66 for the above string version. Could be optimised further. Moral of the story, strings are slow.

    private uint binaryPattern;
    private uint mask;
    private int gapSize;

    public int solution(int N)
    {
        int largestGapSize = 0;
        int gapSize;

        binaryPattern = Convert.ToUInt32(N);
        mask = 1;   // 0000 0000 0000 0001

        // Console.Write("Input is " + inVal.ToString() + " ");
        // Console.Write("binary: " + Convert.ToString(inVal, 2) + " ");

        MaskToNextOne();
        if (mask == 0)
            return largestGapSize;

        do
        {
            MaskToNextZero();
            gapSize = MaskToNextOne();
            
            if (mask == 0)
                return largestGapSize;
            
            if (gapSize > largestGapSize)
                largestGapSize = gapSize;

        } while (mask != 0);

        // Console.Write("Output is " + largestGapSize.ToString());

        return largestGapSize;
    }

    private int MaskToNextOne()
    {
        int gapSize = 0;
        do
        {
            if ((binaryPattern & mask) != 0)
            {
                return gapSize;
            }

            mask <<= 1;
            gapSize++;
        } while (mask != 0);

        return gapSize;
    }

    private void MaskToNextZero()
    {
        do
        {
            if ((binaryPattern & mask) == 0)
            {
                return;
            }

            mask <<= 1;
        } while (mask != 0);
    }

Here is a clear solution. works for all test cases

    public int solution(int N)
    {
        string binaryString = Convert.ToString(N, 2);
        int count = 0;
        int currentCount = 0;
        int strLength = binaryString.Length;
        char[] charArray = binaryString.ToCharArray();

        //check if there is up to two '1's and if there's any '0'
        if (charArray.Count(e => e == '1') < 2 || !charArray.Contains('0'))
        {
            return 0;
        }

        for (int i = 0; i < strLength; i++)
        {
            //check for the first '1' boundary
            if (charArray[i] == '1')
            {
                //start a loop the moment you hit a boundary
                for (int j = i+1; j < strLength; j++)
                {
                    if (charArray[j] == '0')
                    {
                        //increment as you hit '0' consecutively
                        currentCount++;
                    }
                    else {
                        //now you hit a '1' a closing boundary. looking good
                        //now update your count to be the maximum 
                        count = Math.Max(count, currentCount);
                        //reset currentCount, you may need to start another cycle
                        currentCount = 0;
                        //break out of this look to the parent loop
                        break;
                    }
                }
            }

        }

        return count;
    }

Simple solution in JavaScript to return the length of longest binary gap of an integer.

function solution(N) {
  let maxBinGapLength = 0;
  let newBinGapLength = 0
  let count = 0;
  let binS = N.toString(2);
  console.log(binS);
  for (let x = 0; x < binS.length; x++ ) {
    if (binS[x] == '1') {
      if (count > 0) {
        newBinGapLength = count;
        count = 0;
      }
    } else {
      count++;
    }
    maxBinGapLength = Math.max(maxBinGapLength, newBinGapLength);
  }
  return maxBinGapLength;
}

console.log(solution(9)); --> "1001" --> 2
console.log(solution(20)); --> "10100" --> 1
console.log(solution(32)); --> "100000" --> 0
console.log(solution(529)); --> "1000010001" --> 4
console.log(solution(8743742)); --> "100001010110101100111110" --> 4

Solution in C# console app to return the length of longest binary gap of an integer.

Solution.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinaryGap
{
    class Solution
    {
        public int solution(int N)
        {
            int maxBinGapLength = 0, newBinGapLength = 0, count =  0;
            string binStr = Convert.ToString(N, 2);
            for (int x= 0; x < binStr.Length; x++)
            {
                if (binStr[x] == '1')
                {
                    if (count > 0) {
                        newBinGapLength = count;
                        count = 0;
                    }
                } else
                {
                    count++;
                }
                maxBinGapLength = Math.Max(maxBinGapLength, newBinGapLength);
            }
            Console.WriteLine(binStr);
            return maxBinGapLength;
        }
    }
}

Program.cs

using BinaryGap;

Solution binGap = new Solution();
Console.WriteLine(binGap.solution(20));
Console.WriteLine(binGap.solution(32));
Console.WriteLine(binGap.solution(529));

We can go for the bitwise, by this solution we can avoid the binary conversion,

Works for all test cases

public static int BinaryGapSolutionByBitwise(int N)
        {
            int maxLength = 0;
            int currCount = 0;
            bool counting = false;

            while (N > 0)
            {
                if ((N & 1) == 1)
                {
                    counting = true;
                    maxLength = Math.Max(maxLength, currCount);
                    currCount = 0;
                }
                else if (counting)
                {
                    currCount++;
                }

                N >>= 1; 
            }

            return maxLength;
        }