43
\$\begingroup\$

Given an integer n > 0, output the length of the longest contiguous sequence of 0 or 1 in its binary representation.

Examples

  • 6 is written 110 in binary; the longest sequence is 11, so we should return 2
  • 16100004
  • 89311011111015
  • 13373711010001101000000110116
  • 111
  • 99655461001100000001111111010107
\$\endgroup\$
  • 8
    \$\begingroup\$ OEIS A043276 \$\endgroup\$ – alephalpha Jan 13 '17 at 4:45
  • \$\begingroup\$ Can we assume any bound of the size of the integer like 32 bit or 64 bit? \$\endgroup\$ – xnor Jan 13 '17 at 5:55
  • \$\begingroup\$ @xnor yes you can assume the int is 32 bits max \$\endgroup\$ – Arnaud Jan 13 '17 at 6:20

41 Answers 41

30
\$\begingroup\$

Python 2, 46 45 bytes

f=lambda n,k=1:`k`in bin(n^n/2)and-~f(n,k*10)

Try it online!

How it works

By XORing n and n/2 (dividing by 2 essentially chops off the last bit), we get a new integer m whose unset bits indicate matching adjacent bits in n.

For example, if n = 1337371, we have the following.

n    = 1337371 = 101000110100000011011₂
n/2  =  668685 =  10100011010000001101₂
m    = 1989654 = 111100101110000010110₂

This reduces the task to find the longest run of zeroes. Since the binary representation of a positive integer always begins with a 1, we'll try to find the longest 10* string of digits that appears in the binary representation of m. This can be done recursively.

Initialize k as 1. Every time f is executed, we first test if the decimal representation of k appears in the binary representation of m. If it does, we multiply k by 10 and call f again. If it doesn't, the code to the right of and isn't executed and we return False.

To do this, we first compute bin(k)[3:]. In our example, bin(k) returns '0b111100101110000010110', and the 0b1 at the beginning is removed with [3:].

Now, the -~ before the recursive call increments False/0 once for every time f is called recursively. Once 10{j} (1 followed by j repetitions of 0) does not appear in the binary representation of k, the longest run of zeroes in k has length j - 1. Since j - 1 consecutive zeroes in k indicate j matching adjacent bits in n, the desired result is j, which is what we obtain by incrementing False/0 a total of j times.

\$\endgroup\$
  • 2
    \$\begingroup\$ This is really clever! \$\endgroup\$ – CraigR8806 Jan 13 '17 at 12:48
  • 1
    \$\begingroup\$ Wow, that's clever. Never could've thought of it. \$\endgroup\$ – HyperNeutrino Jan 13 '17 at 15:16
  • \$\begingroup\$ Nice trick with the powers of 10, but don't they become longs with an L? \$\endgroup\$ – xnor Jan 14 '17 at 7:58
  • \$\begingroup\$ @xnor Eventually, but that's just a data type limitation. The C, JavaScript, and PHP answers also suffer from this. \$\endgroup\$ – Dennis Jan 14 '17 at 8:03
  • \$\begingroup\$ This would be seriously unmaintainable if used in production. In short (ghehe) golf achieved, hole in one :) \$\endgroup\$ – J.A.K. Jan 15 '17 at 20:44
17
\$\begingroup\$

Python 2, 46 bytes

f=lambda n,r=1:max(r,n and f(n/2,1+~-n/2%2*r))

Try it online

Extracts binary digits from n in reverse by repeatedly taking n/2 and n%2. Tracks the length of the current run r of equal digits by resetting it to 0 if the last two digits are unequal, then adding 1.

The expression ~-n/2%2 is an indicator of whether the last two digits are equal, i.e. n is 0 or 3 modulo 4. Checking the last two digits together turned out shorten than remembering the previous digit.

\$\endgroup\$
14
\$\begingroup\$

05AB1E, 6 bytes

b.¡€gM

Try it online!

Explanation

b       # convert to binary
 .¡     # split at difference
   €g   # map length on each
     M  # take max
\$\endgroup\$
  • 2
    \$\begingroup\$ HA! Finally! A use for , I can stop forcing myself to try to use it. \$\endgroup\$ – Magic Octopus Urn Jan 18 '17 at 21:06
  • \$\begingroup\$ @carusocomputing: Pretty sure I've used it in a couple of answers. \$\endgroup\$ – Emigna Jan 18 '17 at 23:37
9
\$\begingroup\$

Mathematica, 38 bytes

Max[Length/@Split[#~IntegerDigits~2]]&

or

Max[Tr/@(1^Split[#~IntegerDigits~2])]&
\$\endgroup\$
9
\$\begingroup\$

Python, 53 bytes

import re;lambda g:max(map(len,re.findall('1+|0+',bin(g))))

Anonymous lambda function.

\$\endgroup\$
9
\$\begingroup\$

Jelly, 6 bytes

BŒgL€Ṁ

Try it online!

How it works

BŒgL€Ṁ  Main link. Argument: n

B       Binary; convert n to base 2.
 Œg     Group adjacent, identical elements.
   L€   Map length over the groups.
     Ṁ  Take the maximum.
\$\endgroup\$
9
\$\begingroup\$

Ruby, 41 40 bytes

->b{("%b%b"%[b,~b]).scan(/1+/).max.size}

Find longest sequence of '1' in b or its inverse.

Thanks to manatwork for saving 1 byte.

\$\endgroup\$
  • 2
    \$\begingroup\$ Not sure about other versions, but in 2.3.1 there is no need for the space between the %b's. \$\endgroup\$ – manatwork Jan 13 '17 at 11:38
  • \$\begingroup\$ You are right, negative binary numbers start with "..". Thanks. \$\endgroup\$ – G B Jan 13 '17 at 11:44
7
\$\begingroup\$

JavaScript (ES6), 54 bytes

f=(n,r=0,l=1,d=2)=>n?f(n>>1,d^n&1?1:++r,r>l?r:l,n&1):l

A recursive solution with a lot of bit manipulation. n stores the input, r stores the length of the current run, l stores the length of the longest run, and d stores the previous digit.

Test snippet

f=(n,r=0,l=1,d=2)=>n?f(n>>1,d^n&1?1:++r,r>l?r:l,n&1):l

for(var i of [0,1,2,3,4,5,6,7,8,9,16,893,1337371]) console.log(`f(${i}): ${f(i)}`)

\$\endgroup\$
  • 1
    \$\begingroup\$ Same idea, but using more bit operations and exploiting the default conversion of undefined to 0. Feel free to borrow: f=(x,b,n,m)=>x?f(x>>1,x&1,n=x&1^b||-~n,m>n?m:n):m \$\endgroup\$ – edc65 Jan 13 '17 at 8:25
7
\$\begingroup\$

Ruby, 51 44 43 bytes

Function solution.

@manatwork is made of magic

->s{('%b'%s).scan(/0+|1+/).map(&:size).max}
\$\endgroup\$
  • \$\begingroup\$ Does this check for consecutive identical digits or just consecutive 0s? \$\endgroup\$ – ngenisis Jan 13 '17 at 5:01
  • 2
    \$\begingroup\$ Incorrect result for 893. \$\endgroup\$ – orlp Jan 13 '17 at 5:02
  • \$\begingroup\$ @orlp not anymore! :D \$\endgroup\$ – Value Ink Jan 13 '17 at 9:15
  • 1
    \$\begingroup\$ I would combine the 1st and 2nd solutions: ->s{s.to_s(2).scan(/0+|1+/).map(&:size).max}. \$\endgroup\$ – manatwork Jan 13 '17 at 9:51
6
\$\begingroup\$

Python 2, 57 bytes

a=lambda n:n and max((n&-n|~n&-~n).bit_length()-1,a(n/2))

A recursive solution. There might be a shorter form for the bit magic.

\$\endgroup\$
6
\$\begingroup\$

Perl, 43 bytes

#!perl -p
\@a[$a+=$_-1+($_>>=1)&1||-$a]while$_;$_=@a

Counting the shebang as one, input is taken from stdin.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Shebangs count as 0 bytes. \$\endgroup\$ – CalculatorFeline Jan 13 '17 at 18:21
  • \$\begingroup\$ @CalculatorFeline consensus on meta is that #!perl counts as zero, not #!perl -p. \$\endgroup\$ – primo Jan 14 '17 at 0:10
  • \$\begingroup\$ @CalculatorFeline: The -p costs 1, on the assumption that your Perl command line would have an argument anyway (e.g. -e or -M5.010), so you can slip a p in just after one of the hyphens. The #!perl is free (although unnecessary). \$\endgroup\$ – user62131 Jan 14 '17 at 20:04
  • \$\begingroup\$ Good to know. . \$\endgroup\$ – CalculatorFeline Jan 15 '17 at 14:18
5
\$\begingroup\$

Pip, 16 bytes

Seems like there's gotta be a shorter way to get the runs of same digit...

MX#*(TBa`1+|0+`)

Takes input as command-line argument. Try it online!

Explanation

     TBa          1st cmdline arg, To Binary
    (   `1+|0+`)  Find all matches of this regex
  #*              Map length operator to that list
MX                Get the maximum and autoprint it
\$\endgroup\$
5
\$\begingroup\$

Perl 6, 36 bytes

{(.base(2)~~m:g/1+|0+/)».chars.max}

Explanation:

{                                 }   # a lambda
  .base(2)                            # convert the argument to base 2
          ~~m:g/     /                # regex match, with global matching turned on
                1+|0+                 # match one or more 1, or one or more 0
 (                    )».chars        # replace each match by its length
                              .max    # take the maximum number

Try it online.

\$\endgroup\$
4
\$\begingroup\$

Haskell, 79 characters

maximum.map length.group.i

where

import Data.List
i 0=[]
i n=mod n 2:i(div n 2)

Or in ungolfed version:

import Data.List
pcg :: Int -> Int
pcg = maximum . map length . group . intToBin

intToBin :: Int -> [Int]
intToBin 0 = []
intToBin n = n `mod` 2 : intToBin (n `div` 2)

Explanation:

intToBin converts an int to a list of binary digits (lsb first). group groups contiguous sequences, such that [1, 1, 0, 0, 0, 1] becomes [[1, 1],[0, 0, 0],[1]]. maximum . map length calculates for each inner list its length and returns the length of the longest.

Edit: Thanks to @xnor and @Laikoni for saving bytes

\$\endgroup\$
  • 2
    \$\begingroup\$ group isn't in Prelude by default, you need to do import Data.List to use it. \$\endgroup\$ – xnor Jan 13 '17 at 9:56
  • 1
    \$\begingroup\$ Note that you can use guards in place of let: i n|(q,r)<-n`quotRem`2=r:i q. See our Haskell golf tips. quotRem can be divMod. I think you can use i 0=[] as the base case. \$\endgroup\$ – xnor Jan 13 '17 at 10:00
  • 1
    \$\begingroup\$ Using div and mod directly is even shorter: i n=mod n 2:i(div n 2). \$\endgroup\$ – Laikoni Jan 13 '17 at 10:12
3
\$\begingroup\$

Pyth, 7 bytes

heSr8.B

Do run length encode on the binary string, then sort it so that the longest runs come last, then take the first element (the length) of the last element (the longest run) of the list.

In pseudocode:

'  S     ' sorted(
'   r8   '   run_length_encode(
'     .BQ'     bin(input()) ))  \
'he      '   [-1][0]
\$\endgroup\$
3
\$\begingroup\$

J, 21 bytes

[:>./#:#;.1~1,2~:/\#:

Try it online!

Explanation

[:>./#:#;.1~1,2~:/\#:  Input: integer n
                   #:  Binary digits of n
              2   \    For each continuous subarray of 2 digits
               ~:/       Reduce it using not-equals
            1,         Prepend a 1 to those results
     #:                Binary digits of n
        ;.1~           Cut the binary digits at each location with a 1
       #                 Get the length of each cut
[:>./                  Reduce those lengths using maximum and return
\$\endgroup\$
3
\$\begingroup\$

MATLAB 71 bytes

m=1;a=diff(int8(dec2bin(a)));while(any(a==0)),m=m+1;a=diff(a);end;m

This converts integer variable 'a' to a binary int8 array then counts the number of times the result has to be differentiated until there is no zero in the result.

I am new here. Is this sort of input and one-liner allowed by the PCG rules?

\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to PPCG! By default, only functions or full programs (not code snippets) are accepted. In your case that means you need to input a with a=input('');. Also, some golfing advice: ~a instead of a==0. Do you really need int8)? \$\endgroup\$ – Luis Mendo Jan 13 '17 at 11:47
3
\$\begingroup\$

Octave, 31 bytes

@(n)max(runlength(+dec2bin(n)))

Try it online!

Explanation

This is a translation of my MATL answer. My initial plan was a different approach, namely @(n)max(diff(find(diff([0 +dec2bin(n) 0])))). But it turns out that Octave has a runlength function (which I just found out about). By default it outputs only the array of run-lengths, so the desired result is the max of that array. The output of dec2bin, which is a char array (string) containing '0' and '1', needs to be converted to a numeric array using +, because runlength expects numeric input.

\$\endgroup\$
3
\$\begingroup\$

Bash / Unix utilities, 66 65 42 bytes

Thanks to @DigitalTrauma for significant improvements (23 bytes!).

dc<<<`dc -e2o?p|fold -1|uniq -c|sort -n`rp

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ @DigitalTrauma Thanks for the improvements, especially for including fold, which hasn't been in my usual arsenal. \$\endgroup\$ – Mitchell Spector Jan 13 '17 at 22:29
3
\$\begingroup\$

Bash (+coreutils, +GNU grep), 33, 32 bytes

EDITS:

  • Minus 1 byte (removed quotes around grep expression)

Golfed

dc -e2o$1p|grep -Po 1+\|0+|wc -L

Explained

 #Convert to binary
 >dc -e2o893p
 1101111101

 #Place each continuous run of 1es or 0es on its own line
 >dc -e2o893p|grep -Po '1+|0+'
 11
 0
 11111
 0
 1

 #Output the length of the longest line
 >dc -e2o893p|grep -Po '1+|0+'|wc -L
 5

Try It Online!

\$\endgroup\$
  • \$\begingroup\$ AFAIK, grep forms neither part of bash nor coreutils, though is maintained and distributed by its own. Not sure about dc, but it used to be a standalone tool in the GNU world. The only one forming part of coreutils is wc. \$\endgroup\$ – Moreaki Jan 15 '17 at 23:40
  • \$\begingroup\$ @Moreaki, grep is POSIX, so any shell-based answer implies that it is already available. dc is not POSIX but is a standard part of almost every *Nix system around, so it is not normally mentioned as a separate dependency, too. \$\endgroup\$ – zeppelin Jan 16 '17 at 10:08
  • \$\begingroup\$ I reckon we're on two different trains of thoughts here: my point was not if grep was POSIX or not, my point was that the title of your submission to me indicated that one would need bash +coreutils to make your solution work, while this seems not the case. When I read it first, this information was confusing to me. If you try your solution on a macOS shipped bash shell, it won't work; and it does not matter if you installed coreutils or not; you'd need GNU grep to make it work. \$\endgroup\$ – Moreaki Jan 24 '17 at 16:13
  • \$\begingroup\$ @Moreaki, yep, I just imply the GNU system, when I say +coreutils, althrough that is not always the case. I've updated the title to be more precise. \$\endgroup\$ – zeppelin Jan 24 '17 at 16:54
2
\$\begingroup\$

Brachylog, 9 bytes

$b@b:lotl

Try it online!

Explanation

$b          List of binary digits of the input
  @b        Runs of consecutive identical digits in that list
    :lo     Order those runs by length
       tl   Output is the length of the last one
\$\endgroup\$
2
\$\begingroup\$

C#, 106 bytes

n=>{int l=1,o=0,p=0;foreach(var c in System.Convert.ToString(n,2)){o=c!=p?1:o+1;l=o>l?o:l;p=c;}return l;};

Formatted version:

System.Func<int, int> f = n =>
{
    int l = 1, o = 0, p = 0;
    foreach (var c in System.Convert.ToString(n, 2))
    {
        o = c != p ? 1 : o + 1;

        l = o > l ? o : l;

        p = c;
    }

    return l;
};

And an alternative approach accessing the string by index at 118 bytes, with whitespace removed:

System.Func<int, int> f2 = n =>
{
    var s = System.Convert.ToString(n, 2);

    int l = 1, c = 1, i = 0;

    for (; i < s.Length - 1; )
    {
        c = s[i] == s[++i] ? c + 1 : 1;
        l = l < c ? c : l;
    }

    return l;
};
\$\endgroup\$
2
\$\begingroup\$

Javascript, 66 Bytes

x=>Math.max(...x.toString(2).split(/(0+|1+)/g).map(y=>y.leng‌​th))

Thanks to manatwork for the code.

Explanation

x.toString(2)

Convert number to binary string.

split(/(0+|1+)/g)

Split every different character (0 or 1) (this regex captures empty spaces but they can be ignored)

map(y=>y.length)

For each element of the array get its length and put it in the returned array.

...

Convert array to list of arguments ([1,2,3] -> 1,2,3)

Math.max()

Get the largest number out of the arguments.

\$\endgroup\$
  • 1
    \$\begingroup\$ By crediting Value Ink's Ruby solution for the inspiration, this can be transformed into x=>x.toString(2).split(/(0+|1+)/g).map(y=>y.length).sort().pop(). Or the same length: x=>Math.max(...x.toString(2).split(/(0+|1+)/g).map(y=>y.length)). \$\endgroup\$ – manatwork Jan 13 '17 at 11:34
  • 3
    \$\begingroup\$ I think you may have to add a predicate to the sort function sort((a,b)=>b-a). By default, the sort function places 10 in between 1 and 2. \$\endgroup\$ – Mama Fun Roll Jan 13 '17 at 14:44
  • \$\begingroup\$ Or you could use Math.max, as manatwork suggested. \$\endgroup\$ – Mama Fun Roll Jan 13 '17 at 14:45
  • \$\begingroup\$ Wtf, but they're numbers. JS please. \$\endgroup\$ – user64039 Jan 13 '17 at 15:38
2
\$\begingroup\$

Wonder, 27 bytes

max.map#len.mstr`0+|1+`g.bn

Usage:

(max.map#len.mstr`0+|1+`g.bn)123

Converts to binary, matches each sequence of 0's and 1's, gets the length of each match, and gets the maximum.

\$\endgroup\$
  • \$\begingroup\$ Does this convert the input to binary? \$\endgroup\$ – Laikoni Jan 13 '17 at 14:53
  • \$\begingroup\$ oooooh I missed that part. Quick fix :P \$\endgroup\$ – Mama Fun Roll Jan 13 '17 at 14:58
2
\$\begingroup\$

Batch, 102 bytes

@set/a"n=%1/2,d=%1%%2,r=1+(%3+0)*!(0%2^d),l=%4-(%4-r>>5)
@if not %n%==0 %0 %n% %d% %r% %l%
@echo %l%

Port of @edc65's answer. %2..%4 will be empty on the first call, so I have to write the expressions in such a way that they will still work. The most general case is %3 which I had to write as (%3+0). %2 is easier, as it can only be 0 or 1, which are the same in octal, so 0%2 works here. %4 turned out to be even easier, as I only need to subtract from it. (%4-r>>5) is used to compare l with r as Batch's set/a doesn't have a comparison operator.

\$\endgroup\$
2
\$\begingroup\$

Dyalog APL, 22 bytes

Anonymous function train

⌈/∘(≢¨⊢⊂⍨1,2≠/⊢)2⊥⍣¯1⊢

⌈/∘(... The maximum of the results of the following anonymous function-train...

≢¨  the tally of each

⊢⊂⍨ partition of the argument, where the partitioning is determined by the ones in

1, one prepended to

2≠/ the pairwise unequal of

 the argument

) applied to

2⊥⍣¯1 from-base-2 applied negative one times (i.e. to-base-2, once) to

 the argument

TryAPL online!

\$\endgroup\$
2
\$\begingroup\$

Japt, 15 bytes

2o!q¢ c ml n gJ

Test it online! or Verify all test cases at once.

How it works

                 // Implicit: U = input integer, J = -1
2o               // Create the range [0...2), or [0,1].
  ! ¢            // Map each item Z in this range to U.s(2)
   q             //                                        .q(Z).
                 // This returns the runs of 1's and 0's in the binary
                 // representation of U, respectively.
      c          // Flatten into a single list.
        ml       // Map each item Z to Z.length.
           n gJ  // Sort the result and grab the item at index -1, or the last item.
                 // This returns the largest element in the list.
                 // Implicit: output result of last expression
\$\endgroup\$
2
\$\begingroup\$

R, 45 34 bytes

max(rle(miscFuncs::bin(scan()))$l)

Fixed a silly misunderstanding thanks to @rturnbull and @plannapus.

\$\endgroup\$
  • \$\begingroup\$ Perhaps I'm missing something, but isn't the input supposed to be an integer, not a binary number? And we're looking for the maximum run of 0 or of 1, not just 0, right? \$\endgroup\$ – rturnbull Jan 13 '17 at 18:08
  • \$\begingroup\$ @plannapus I don't know honestly. Must have missed the spec completely. Fixed now. \$\endgroup\$ – Billywob Jan 26 '17 at 13:45
2
\$\begingroup\$

PowerShell, 78 74 73 bytes

([regex]::Matches([convert]::ToString("$args",2),'0+|1+')|% Le*|sort)[-1]

Try it online!

Ugh those .Net methods.

This just uses a regex to find (and match) contiguous sequences of ones and zeroes, then it takes the Length property (with a new pattern I found that uses a little known parameter set of ForEach-Object, to save 1 byte) of the resulting match objects, sorts them, and outputs the last one (the largest).

\$\endgroup\$
1
\$\begingroup\$

J, 27 bytes

>./>#&.>((1,2~:/\[)<;.1])#:

A slightly different (and unfortunately longer) approach to miles's answer.

Usage:

    >./>#&.>((1,2~:/\[)<;.1])#:893
5

Explanation

>./>#&.>((1,2~:/\[)<;.1])#:
                         #: Convert to base 2
        (               )   A fork
                       ]    Previous result
         (1,2~:/\[)         Find where each new sequence begins
                   <;.1     Cut the string of integers based on where each sequence begins and box them
    #&.>                    Count under open - open each box and count the items in it
>./>                        Open all the boxes and find the maximum value
\$\endgroup\$
  • \$\begingroup\$ I don't think this is valid--it isn't a function and so is a snippet. \$\endgroup\$ – Conor O'Brien Jan 13 '17 at 15:23
  • \$\begingroup\$ @ConorO'Brien Okay, I'll look at it again later. \$\endgroup\$ – Gareth Jan 13 '17 at 15:43

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.