49
\$\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\$
3
  • 8
    \$\begingroup\$ OEIS A043276 \$\endgroup\$
    – alephalpha
    Jan 13, 2017 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, 2017 at 5:55
  • \$\begingroup\$ @xnor yes you can assume the int is 32 bits max \$\endgroup\$
    – Arnaud
    Jan 13, 2017 at 6:20

54 Answers 54

32
\$\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\$
5
  • 2
    \$\begingroup\$ This is really clever! \$\endgroup\$
    – CraigR8806
    Jan 13, 2017 at 12:48
  • 1
    \$\begingroup\$ Wow, that's clever. Never could've thought of it. \$\endgroup\$
    – hyper-neutrino
    Jan 13, 2017 at 15:16
  • \$\begingroup\$ Nice trick with the powers of 10, but don't they become longs with an L? \$\endgroup\$
    – xnor
    Jan 14, 2017 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, 2017 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, 2017 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
  • 2
    \$\begingroup\$ HA! Finally! A use for , I can stop forcing myself to try to use it. \$\endgroup\$ Jan 18, 2017 at 21:06
  • \$\begingroup\$ @carusocomputing: Pretty sure I've used it in a couple of answers. \$\endgroup\$
    – Emigna
    Jan 18, 2017 at 23:37
9
\$\begingroup\$

Mathematica, 38 bytes

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

or

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

Python, 53 bytes

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

Anonymous lambda function.

\$\endgroup\$
0
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
  • 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, 2017 at 11:38
  • \$\begingroup\$ You are right, negative binary numbers start with "..". Thanks. \$\endgroup\$
    – G B
    Jan 13, 2017 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
  • 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, 2017 at 8:25
7
\$\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\$
4
  • \$\begingroup\$ Shebangs count as 0 bytes. \$\endgroup\$ Jan 13, 2017 at 18:21
  • \$\begingroup\$ @CalculatorFeline consensus on meta is that #!perl counts as zero, not #!perl -p. \$\endgroup\$
    – primo
    Jan 14, 2017 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, 2017 at 20:04
  • \$\begingroup\$ Good to know. . \$\endgroup\$ Jan 15, 2017 at 14:18
7
\$\begingroup\$

Ruby, 51 44 43 bytes

Function solution.

@manatwork is made of magic

->s{('%b'%s).scan(/0+|1+/).map(&:size).max}
\$\endgroup\$
4
  • \$\begingroup\$ Does this check for consecutive identical digits or just consecutive 0s? \$\endgroup\$
    – user61980
    Jan 13, 2017 at 5:01
  • 2
    \$\begingroup\$ Incorrect result for 893. \$\endgroup\$
    – orlp
    Jan 13, 2017 at 5:02
  • \$\begingroup\$ @orlp not anymore! :D \$\endgroup\$
    – Value Ink
    Jan 13, 2017 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, 2017 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\$
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\$
3
  • 2
    \$\begingroup\$ group isn't in Prelude by default, you need to do import Data.List to use it. \$\endgroup\$
    – xnor
    Jan 13, 2017 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, 2017 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, 2017 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\$
1
  • 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, 2017 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
  • 1
    \$\begingroup\$ @DigitalTrauma Thanks for the improvements, especially for including fold, which hasn't been in my usual arsenal. \$\endgroup\$ Jan 13, 2017 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\$
4
  • \$\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\$
    – ikaerom
    Jan 15, 2017 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, 2017 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\$
    – ikaerom
    Jan 24, 2017 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, 2017 at 16:54
3
\$\begingroup\$

Vyxal G, 4 bytes

bøef

Try it Online!

Abuses the G flag which returns the maximum value of the item on top of the stack.

b      # convert input to binary
  øef  # run_length_encoding and flatten 2D -> 1D
       # Implicitly take the largest value in the flattened array
\$\endgroup\$
3
\$\begingroup\$

J-uby, 41 38 bytes

~:digits&2|:slice_when+:!=|:*&:+@|:max

Attempt This Online!

\$\endgroup\$
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\$
4
  • 2
    \$\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, 2017 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\$ Jan 13, 2017 at 14:44
  • \$\begingroup\$ Or you could use Math.max, as manatwork suggested. \$\endgroup\$ Jan 13, 2017 at 14:45
  • \$\begingroup\$ Wtf, but they're numbers. JS please. \$\endgroup\$
    – user64039
    Jan 13, 2017 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\$
2
  • \$\begingroup\$ Does this convert the input to binary? \$\endgroup\$
    – Laikoni
    Jan 13, 2017 at 14:53
  • \$\begingroup\$ oooooh I missed that part. Quick fix :P \$\endgroup\$ Jan 13, 2017 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\$
2
  • \$\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, 2017 at 18:08
  • \$\begingroup\$ @plannapus I don't know honestly. Must have missed the spec completely. Fixed now. \$\endgroup\$
    – Billywob
    Jan 26, 2017 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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