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;
        }
    }
}

Is it really working for n=32?

This solution does not work for numbers like 32, 20, because a binary gap represents the number of '0' between two '1' .
Ex: 20 is '10100'. The binary gap should be equal to the value of 1, but this solution returns the value 2, because it does not account for the fact that there is no '1' bit at the end

I solved the issue with numbers like 32 and 20, adding a validation if the end number has '1', here's my solution:

public class Solution {

public int solution(int N) {
    string bits = Convert.ToString(N, 2);
    int size = 0;
    int sizeReal = 0;
    int cont = 0;
    for (int i = 0; i < bits.Length; i++)
    {
        if (bits[i] == '0')
        {
            if (cont > 0) cont++;
            else cont = 1;
        } else cont = 0;
        if (cont > size) size = cont;
        if (bits[i] == '1' && size > sizeReal) sizeReal = size;
    }
    return sizeReal;
}

}

class Program
{
static void Main(string[] args)
{
var bin = Convert.ToString(20, 2);
int CurrentCount = 0;
int previousCount = 0;
int position = 0;
foreach(var c in bin)
{
if (c == '0')
CurrentCount++;
else
{
if (CurrentCount > previousCount)
{
position = CurrentCount ;
previousCount = CurrentCount;
}
CurrentCount = 0;
}
}
Console.WriteLine(position);
}
}

Here is my solution with 100 percent correctness and performance.

public int solution(int N) {
string bits = Convert.ToString(N, 2);
int maxDiff = 0, newDiff = 0;
for(int i = 0; i< bits.Length; i++)
{
if(bits[i] == '0')
{
newDiff++;
}
else
{
maxDiff = Math.Max(newDiff, maxDiff);
newDiff = 0;
}
}
return maxDiff;
}

Here is a solution using LINQ, that handles all scenarios

public static int solution(int N)
{
if (N <= 0)
{
return 0;
}

        string binary = Convert.ToString(N, 2);
                    
        if (binary.Count(x => (x == '1')) == 1)
        {
            return 0;
        }
        else
        {
            string[] result = binary.Split('1');
            int maxLength = result.Max(x => x.Length);
            string[] longestStrings = result.Where(x => x.Length == maxLength).ToArray();
            
            return longestStrings.First().Length;
        }
    }

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;
        }