5
\$\begingroup\$

I am aware this problem has been asked before but in java e.g Printing longest sequence of zeroes. This is a similar problem but in C#. A brief explanation of the problem is to find the longest sequence of zeroes in a binary representation of an Integer. For instance, the Integer 529 in binary gives 1000010001 and the longest sequence of zeroes is 4. So far I have achieved this using the following code

using System.IO;
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    public static int Solution(int N)
    {
        List<int> occurenceCount = new List<int>();
        int Counter=0,value;

        if(N == 0)
        {
            Console.WriteLine(0);
            return 0;
        }

        else{
            string binaryRep = Convert.ToString(N,2);

            // find the first occurence of 1 
            int FirstIndex = binaryRep.IndexOf("1");

            // find the last occurence of 1
            int LastIndex = binaryRep.LastIndexOf("1");

            for(int i = FirstIndex; i<LastIndex+1;)
            {

                value = i;

                while(binaryRep[value++] != '1' )
                {
                  Counter = Counter+1;
                }
                occurenceCount.Add(Counter);
                i= value;
               Counter=0;
            }
        return occurenceCount.Max();
        }
    }
    static void Main()
    {
       Console.WriteLine(Solution(1041));
    }
}

Brief description of the code: If the Integer passed is 0, then 0 is returned else the longest sequence. The convert.ToString() gives the binary representation. To improve the performance, I keep track of the index of the first 1 and the last index of 1 and use this in the for loop. In the while loop, once a 0 is encountered in between two 1's then a counter is incremented until a 1 is encountered and later on added to the List. I would appreciate if any one can tell me how to improve on this.

\$\endgroup\$
  • 3
    \$\begingroup\$ A suggestion for your next challenge. Can you write a generic method that takes an IEnumerable<int> and returns an IEnumerable<int> where each int is the "run length" of the numbers? So for example given the sequence 1, 1, 1, 2, 2, 5, 3, 3, 3, 3, 2 the result would be 3, 2, 1, 4, 1 because there are 3 ones, 2 twos, 1 five, 4 threes and 1 two. Once you have written that program, do you see how you can use it to easily solve this problem? \$\endgroup\$ – Eric Lippert May 11 '16 at 16:13
  • \$\begingroup\$ @EricLippert That's a fun problem! :D I think the Clojure one-liner also solves the problem (I made need code review on this one. :P) (apply max (map count (set (string/split "1000010001" #"1")))) \$\endgroup\$ – Jeel Shah May 11 '16 at 18:02
  • \$\begingroup\$ Like all other problems in the world, this can be solved with a regex: Look for (0*), walk through all matches and select the longest one. \$\endgroup\$ – Traubenfuchs May 12 '16 at 9:06
10
\$\begingroup\$

Unless performance is somehow critical, you'd do far better by just making use of String.Split on '1' after getting a binary representation. Then you can search for the longest string in that array. The current implementation is very low level and hard to easily understand.

A programmer who sees the code as it is now would have to invest time to understand how it works, whereas relying on (even if slower) a few library calls can make an algorithm easier to understand for programmers, thus being of more value than the faster, low level algorithm. It's also faster to write such things and less likely to contain bugs because most of the actual work is done by the standard libraries, which are thoroughly tested by other programmers.

\$\endgroup\$
  • \$\begingroup\$ I have included a brief description of the code to aid understanding. \$\endgroup\$ – Siobhan May 11 '16 at 12:55
  • \$\begingroup\$ @TolaniJaiye-Tikolo thanks, but what I mean is that a programmer who sees your code would have to invest time to understand how it works, whereas relying on (even if slower) a few library calls can make an algorithm easier to understand for this programmer, thus being of more value than the faster, low level algorithm. \$\endgroup\$ – Pimgd May 11 '16 at 12:57
  • \$\begingroup\$ But in all honesty, JNS's answer is a better approach than mine, if it works, which I think it does \$\endgroup\$ – Pimgd May 11 '16 at 12:57
  • 1
    \$\begingroup\$ I really like this answer. Really shows that programming is all about managing complexity. \$\endgroup\$ – xofz May 11 '16 at 20:43
7
\$\begingroup\$

What about:

var value = 529;
var count = 0;
var countMax = 0;
while(value > 0)
{
    count = value % 2 == 0 ? count + 1 : 0;
    value /= 2;
    countMax = Math.Max(count, countMax);
}
// result in: countMax;

[Edit: Version that supports also negative ints]

var value = 529;
var count = 0;
var countMax = 0;
var factor = value < 0 ? -1 : 1;
while((value * factor) > 0)
{
    count = value % 2 == 0 ? count + 1 : 0;
    value /= 2;
    countMax = Math.Max(count, countMax);
}
// result in: countMax;

[Edit2: added explanation]

Converting the integer to a string of bits and count the linked zeros using string operations is one option. However, it needs lots of code and is not really performant.

Another option is to check if the number is even. If so, the last bit is not set ('0'). Dividing the number with 2 removes the last bit, so that we can check the next bit... and so on.

\$\endgroup\$
  • 6
    \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. - I like your answer, but with an explanation it'd be a lot better - I've already upvoted your answer. \$\endgroup\$ – Pimgd May 11 '16 at 12:58
  • 2
    \$\begingroup\$ Looking at this again, any reason you go for division and not bitshifting? \$\endgroup\$ – Pimgd May 11 '16 at 13:05
  • 1
    \$\begingroup\$ The problem with bitshifting is, that for signed integers, the sign-bit will be preserved. see also: Shifting the sign bit in .NET. Therefore I cant find a simple solution for negative numbers. \$\endgroup\$ – JanDotNet May 11 '16 at 13:50
  • 1
    \$\begingroup\$ The simple solution for negative numbers is that when you hit -1 there are no zeros left in the representation. \$\endgroup\$ – Peter Taylor May 11 '16 at 14:20
  • 3
    \$\begingroup\$ Unfortunately, the problem statement is supposed to be the zeros between two 1s - it's also limited to positive integers. I still +1'd as you have solved the problem as posed in this question (although the code adheres to the fuller specification). \$\endgroup\$ – RobH May 11 '16 at 14:33
4
\$\begingroup\$

Stylistically there is room for improvement. With C# you are encouraged to use meaningful names. Also parameters and variables should begin with a lowercase. That would change this:

public static int Solution(int N)

To

public static int Solution(int number)

While your use of braces is decent, you have a mixup of spacing. Let your code "breath" by having spaces around things, but don't have a white line before an else. That would change this:

if(N == 0)
{
    Console.WriteLine(0);
    return 0;
}

else{

To this:

if (N == 0)
{
    Console.WriteLine(0);
    return 0;
}
else
{

Each variable declaration should be on its own line. This changes this:

int Counter=0,value;

To

int counter = 0;
int value;

Your methods should be singular in purpose. In your OP, Solution finds the solution and also writes to the console. It really should be just to find the solution, and let Main take care of the display.

And it could be much smaller. Taking @Pimgd 's suggestion, the code could be reduced to:

public static int Solution(int number)
{
    if (number == 0)
    {
        return 0;
    }
    return Convert.ToString(number, 2).Split(new char[] { '1' }).Max(x => x.Length);
}

Or even this one-liner:

public static int Solution(int number) => number == 0 ? 0 : Convert.ToString(number, 2).Split(new char[] { '1' }).Max(x => x.Length);

Though as a one-liner it looks a bit jumbled. The guiding rule of thumb is to use the code that is easiest to read by another developer.

\$\endgroup\$
  • \$\begingroup\$ Your first comment is about names - you recommend changing the parameter name, but I think Solution() as a method name is a worse offender. number as a parameter name offers nothing over n. \$\endgroup\$ – adelphus May 11 '16 at 19:02
2
\$\begingroup\$

Others have already provided alternative solutions. I'll provide a small review of your original code instead:

Names

Solution is not a descriptive name. Renaming that method to something like MaxConsecutiveZeroBits will make its purpose more clear.

Some of your variables start with a capital letter, others do not. Normally CamelCase is used for type and method names, whereas camelCase is used for parameters and local variables. Being consistent makes your code easier to read.

Variable declaration

In C# there's no need to declare variables at the start of a method. I'd declare them in the smallest possible scope, just before they are actually used. This takes less skipping around, which makes the code easier to read.

Improvements

You don't need to keep a list of counts. You only need to keep track of the maximum count so far. After counting a sequence of zeroes, compare it against the current maximum count. If it's bigger, store it. Otherwise, discard it.

With the above change, you don't need to check up to LastIndex + 1 to prevent the list from staying empty, so that + 1 can be left out. Also, you can start at FirstIndex + 1, because the character at FirstIndex is certainly a 1.

Other changes

Counter = Counter + 1 can be rewritten as Counter += 1, or Counter++.

The value variable serves no useful purpose. You can just use i directly instead.

I'd remove that Console.WriteLine call from Solution. It's useful during development, but also ties your code to requiring a console, and causes it to have unexpected side-effects.

The if (N == 0) block immediately returns, so the rest of the code doesn't really need to be put in an else block. Not much of a problem here, but not using else blocks in methods that have multiple 'early-out' checks can prevent a lot of nesting, improving readability.

\$\endgroup\$
  • 1
    \$\begingroup\$ The first thing you described as CamelCase is more commonly referred to as PascalCase. Camel-case generally means the first letter is lower-case. \$\endgroup\$ – Darrel Hoffman May 11 '16 at 21:48
2
\$\begingroup\$

Bug

What none of the four existing answers have pointed out is that your code has a bug. Solution(8) should give 3 but actually gives 0. The problem is that looping only until the last '1' fails to take into account the possibility that the longest run of zeros is after the last '1'.

Priorities

There's often a tradeoff between performance and readability. It's extremely unlikely that this method is going to be a major bottleneck, so Pimgd's solution in two lines which values readability above all else is likely to be the best option. But if you (and your team, if relevant) are willing to sacrifice readability for performance, bit-bashing will be faster than converting to a string and then processing the string. But there are still readability/performance tradeoffs within bit-bashing. There's the simple linear approach proposed by JNS, which can be simplified to

    public static int LongestZeroRun(int n)
    {
        int longest = 0, current = 0;
        while (n != n >> 1)
        {
            current = ((n & 1) == 0) ? current + 1 : 0;
            if (current > longest) longest = current;
            n = n >> 1;
        }
        return longest;
    }

and correctly handle negative inputs.

But for really extreme cases, it's possible to process multiple bits at once. E.g.

    private static readonly int[] DeBruijn = new int[]
    {
        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };
    public static int CountTrailingZeroes(int n)
    {
        return DeBruijn[(((n & -n) * 0x077cb531) >> 27) & 31];
    }

    public static int LongestZeroRun(int n)
    {
        int longest = 0;
        while (n != n >> 1)
        {
            int current = CountTrailingZeroes(n);
            if (current > longest) longest = current;
            n >>= current;
            n >>= CountTrailingZeroes(~n);
        }
        return longest;
    }
\$\endgroup\$
  • 1
    \$\begingroup\$ Could you please explain the last code example? \$\endgroup\$ – JanDotNet May 11 '16 at 15:47
  • 2
    \$\begingroup\$ "Solution(8) should give 3 but actually gives 0." Their finding numbers between ones. as eight doesn't end in a one, and only has a single one. It should be zero. \$\endgroup\$ – Peilonrayz May 11 '16 at 16:09
  • \$\begingroup\$ Good spots Joe and Peter , I didn't take into consideration that scenario \$\endgroup\$ – Siobhan May 11 '16 at 16:18
  • \$\begingroup\$ @JNS It uses a De Bruijn sequence. It's a bit hack. \$\endgroup\$ – Cole Johnson May 12 '16 at 5:36
1
\$\begingroup\$

I'm not at my programming machine now so I can't write and test code. But here's a sketch of a shift differential approach.

  1. Shifted xor gives 1 at all positions of transition either 0 to 1 or 1 to 0 ( compare to a [1 -1] digital filter running over the bits ):

    (x<<1)^x
    
  2. One variable stores first zero and one first one (anding with bitwise inversion)

  3. Sequence of ffs ( find first set ) which is a hardware operation in most modern CPUs. Largest difference of consecutive positions will be the number we want. Stop when both numbers are zero.


PRO Good performance for numbers with many consecutive ones and zeros.

CON This will likely be bad for numbers with many toggles between 0 and 1.

BUT We can do a population count (popcnt - often also in hardware) on numbers in 2) to count the number of fields of 0s and 1s and then decide wether to use this method or some other.


EDIT Oh no this was for C#, I was going all performance geeky here with C and C++ considerations and even lower stuff. Maybe I can delete it if you find it too off topic.

\$\endgroup\$

protected by Jamal Nov 24 '17 at 2:30

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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