Binary Substrings

Question

Inspired by the fourth problem from BMO2 2009.

Given a positive integer n as input or a parameter, return the number of positive integers whose binary representations occur as blocks in the binary expansion of n.

For example, 13 -> 6 because 13 in binary is 1101 and it has substrings 1101, 110, 101, 11, 10, 1. We do not count binary numbers that start with zero and we do not count zero itself.

Test Cases

13 -> 6
2008 -> 39
63 -> 6
65 -> 7
850 -> 24
459 -> 23
716 -> 22
425 -> 20
327 -> 16

You may take in n as any of the following:

• an integer
• a list of truthy/falsy values for the binary representation
• a string for the binary representation
• a base 10 string (though I'm not sure why anyone would do this)

Make your code as short as possible.

Answer 1

Python 3, 54 50 bytes

lambda n:sum(bin(i)[2:]in bin(n)for i in range(n))

Thanks to Rod and Jonathan Allan for saving four bytes.

Answer 2

Jelly, 4 bytes

ẆQSḢ

Try it online!

Takes input as list of 0s and 1s.

Try it online with numbers!

Explanation:

ẆQSḢ Argument: B = list of bits, e.g. [1, 1, 0, 1]
Ẇ    Get B's non-empty sublists (i.e. [[1], [1], [0], [1], [1, 1], [1, 0], [0, 1], [1, 1, 0], [1, 0, 1], [1, 1, 0, 1]])
 Q   Keep first occurrences (i.e. [[1], [0], [1, 1], [1, 0], [0, 1], [1, 1, 0], [1, 0, 1], [1, 1, 0, 1]])
  S  Reduce by vectorized addition (i.e. [6, 4, 1, 1])
   Ḣ Pop first element (i.e. 6)

Proof it works:

This program gets an input number, N. The first thing this product does is, of course, take the substrings of N₂ (N in base 2). This includes duplicate substrings starting with either 0 or 1.

After that, we simply take the unique substrings by keeping only the first occurrence of each value in the substring list.

Then, this program sums the first elements of the lists together, then the second elements, then the third, fourth, etc. and if one of the lists has no such element 0 is assumed. What the challenge asks is effectively How many unique substrings starting with 1 does this number have in its binary form?. Since every first element which is to be counted is 1, we can simply sum instead of filtering for appropriate substrings.

Now, the first element of the resulting list of the summation described above holds the count of the first bits of the substrings, so we simply pop and finally return it.

Answer 3

Octave, 62 61 bytes

@(n)sum(arrayfun(@(t)any(strfind((g=@dec2bin)(n),g(t))),1:n))

Try it online!

Explanation

For input n, the code tests all numbers from 1 to n to see if their binary representation is a substring of the binary representation of the input.

@(n)                                                          % Anonymous function of n
        arrayfun(                                      ,1:n)  % Map over range 1:n
                 @(t)                                         % Anonymous function of t
                         strfind(               ,    )        % Indices of ...
                                                 g(t)         % t as binary string ...
                                 (g=@dec2bin)(n)              % within n as binary string
                     any(                             )       % True if contains nonzero
    sum(                                                    ) % Sum of array

Answer 4

05AB1E, 5 bytes

Takes input as a binary string.
The header converts integer input to binary for ease of testing.

ŒCÙĀO

Try it online!

Explanation

Π       # push all substrings of input
 C       # convert to base-10 int
  Ù      # remove duplicates
   Ā     # truthify (convert non-zero elements to 1)
    O    # sum

Answer 5

Perl 5, 36 + 1 (-p) = 37 bytes

/.*(.+?)(?{$k{0|$1}++})(?!)/;$_=%k-1

Try it online!

Takes input as a binary string.

Answer 6

PowerShell, 103 92 82 bytes

param($s)(($s|%{$i..$s.count|%{-join$s[$i..$_]};$i++}|sort -u)-notmatch'^0').count

Try it online!

Takes input as an array of 1 and 0 (truthy and falsey in PowerShell). Loops through $s (i.e., how many elements in the input array). Inside the loop, we loop from the current number (saved as $i) up to $s.count. Each inner loop, we -join the array slice into a string. We then sort with the -unique flag (which is shorter than select with the -unique flag and we don't care whether they're sorted or not), take those that don't start with 0, and take the overall .count. That's left on the pipeline and output is implicit.

Answer 7

JavaScript (ES6), 55 bytes

f=(s,q="0b"+s)=>q&&s.includes((q--).toString(2))+f(s,q)

Takes input as a binary string.

Here's a sad attempt at doing it with numbers and recursive functions:

f=(n,q=n)=>q&&(g=n=>n?n^q&(h=n=>n&&n|h(n>>1))(q)?g(n>>1):1:0)(n)+f(s,q-1)

Old approach, 74 bytes

s=>(f=s=>+s?new Set([+s,...f(s.slice(1)),...f(s.slice(0,-1))]):[])(s).size

Also takes input as a binary string.

Answer 8

Jelly, 5 bytes

ẆḄQṠS

Try it online!

Takes input as a list of 1s and 0s. The footer in the link applies the function to each of the examples in the post.

Jonathan Allan pointed out that ẆḄQTL is 5 byte alternative which uses the T atom which finds the indices of all truthy elements.

Explanation

Take bin(13)=1101 as an example. Input is [1,1,0,1]

ẆḄQṠS
Ẇ       All contiguous sublists -> 1,1,0,1,11,10,01,110,101,1101 (each is represented as a list)
 Ḅ      From binary to decimal. Vectorizes to each element of the above list -> 1,1,0,1,3,2,1,6,5,13
  Q     Unique elements
   Ṡ    Sign. Positive nums -> 1 , 0 -> 0.
    S   Sum

Took the "truthify" (sign in this case) idea from the 05AB1E answer

Answer 9

R, 88 77 bytes

function(x)sum(!!unique(strtoi(mapply(substring,x,n<-1:nchar(x),list(n)),2)))

Try it online!

Takes input as a binary string.

using mapply, generates an array of all substrings of the input. strtoi converts them as base 2 integers, and I take the sum of the logical conversion (!!) of entries in the result.

Answer 10

Python 2,  118  81 bytes

Thanks to @Rod for saving 37 bytes!

lambda n:len({int(n[i:j+1],2)for i in range(len(n))for j in range(i,len(n))}-{0})

Takes input as a binary string.

Try it online!

Python 2, 81 bytes

Thanks to @Rod!

lambda n:len({n[i:j+1]for i in range(len(n))for j in range(i,len(n))if'1'==n[i]})

Takes input as a binary string.

Try it online!

Answer 11

Pyth, 8 bytes

l #{vM.:

Try it here!

Takes input as a binary string.

.: generates all the substrings, vM evaluates each (that is, it converts each from binary), { deduplicates, <space># filters by identity and l gets the length.

Answer 12

Retina, 37 29 bytes

.+
*
+`(_+)\1
$1#
#_
_
wp`_.*

Try it online! I just had to try out Retina 1.0's w modifier. Edit: Saved 8 bytes thanks to @MartinEnder. Explanation:

.+
*

Convert from decimal to unary.

+`(_+)\1
$1#
#_
_

Convert from unary to binary, using # for 0 and _ for 1.

wp`_.*

Generate substrings that begin with 1, I mean, _. The w modifier then matches all substrings, not just the longest one at each starting _, while the p modifier deduplicates the matches. Finally as this is the last stage the count of matches is implicitly returned.

Answer 13

Wolfram Language (Mathematica), 35 bytes

Counting unique subsequences of the binary representation that start with one, although I'm not sure this code even needs an explanation.

Union@Subsequences@#~Count~{1,___}&

Try it online!

Answer 14

Perl 6, 47 bytes

->\n{+grep {n.base(2).contains(.base: 2)},1..n}

Try it online!

Answer 15

Julia 0.6, 37 bytes

~n=sum(contains.([bin(n)],bin.(1:n)))

Try it online!

Juliafication of the Python answer by J843136028 using . for element-wise function application with broadcasting. (link)

Answer 16

Java, 232 bytes

String b=toBin(n);
l.add(b);
for(int i=1;i<b.length();i++){
for(int j=0;j<=b.length()-i;j++){
String t="";
if((""+b.charAt(j)).equals("0"))continue;
for(int k=0;k<i;k++){
t+=""+b.charAt(j+k);
}
if(!l.contains(t))l.add(t);
}
}
return l.size();

Where n is the input, b is the binary representation and l is a list of all the substrings. First time posting here, definitely need to improve, and feel free to point out any mistakes! Slightly edited for readability.

Answer 17

Ruby 41 36 27 bytes

Takes binary string as input

Is ultra-inefficient

->n{(?1..n).count{|j|n[j]}}

Partly inspired by this python 3 answer

Try it online!

Answer 18

Attache, 35 bytes

`-&1@`#@Unique@(UnBin=>Subsets@Bin)

Try it online!

Equivalently:

{#Unique[UnBin=>Subsets[Bin[_]]]-1}

Explanation

I will explain the second version, as it is easier to follow (being explicit):

{#Unique[UnBin=>Subsets[Bin[_]]]-1}
{                                 }   lambda: _ = first argument
                        Bin[_]        convert to binary
                Subsets[      ]       all subsets of input
         UnBin=>                      map UnBin over these subsets
  Unique[                      ]      remove all duplicates
 #                              -1    size - 1 (since subsets is improper)

Answer 19

C++, 110 bytes

#include<set>
std::set<int>s;int f(int n){for(int i=1;i<n;i+=i+1)f(n&i);return n?s.insert(n),f(n/2):s.size();}

This is a recursive function. We use a std::set to count values, ignoring duplicates. The two recursive calls mask bits off the left (f(n&i)) and off the right (f(n/2)), eventually producing all the substrings as integers.

Note that if you want to call it again, s must be cleared between calls.

Test program

#include <cstdlib>
#include <iostream>

int main(int, char **argv)
{
    while (*++argv) {
        auto const n = std::atoi(*argv);
        s={};
        std::cout << n << " -> " << f(n) << std::endl;
    }
}

Results

./153846 13 2008 63 65 850 459 716 425 327
13 -> 6
2008 -> 39
63 -> 6
65 -> 7
850 -> 24
459 -> 23
716 -> 22
425 -> 20
327 -> 16

Answer 20

Java 8, 160 159 158 bytes

import java.util.*;b->{Set s=new HashSet();for(int l=b.length(),i=0,j;i<l;i++)for(j=l-i;j>0;s.add(new Long(b.substring(i,i+j--))))s.add(0L);return~-s.size();}

Input as binary-String.
There must be a shorter way.. >.>

Explanation:

Try it online.

import java.util.*;          // Required import for Set and HashSet
b->{                         // Method with String as parameter and integer as return-type
  Set s=new HashSet();       //  Create a Set
  for(int l=b.length(),      //  Set `l` to the length of the binary-String
      i=0,j;i<l;i++)         //  Loop from 0 up to `l` (exclusive)
    for(j=l-i;j>0;           //   Inner loop from `l-i` down to `0` (exclusive)
      s.add(new Long(b.substring(i,i+j--))))
                             //    Add every substring converted to number to the Set
      s.add(0L);             //    Add 0 to the Set
  return~-s.size();}         //  Return the amount of items in the Set minus 1 (for the 0)

Answer 21

J, 34 bytes

f=.3 :'<:#~.,(#:i.2^##:y)#.;.1#:y'

Try it online!

Answer 22

J, 15 bytes

#.\\.#@=@-.&,0:

Input is a binary list. Try it online!

#.\\.               Convert every substring to decimal
         -.&,0:     Flatten and remove the 0s.        
     #@=            How many unique elements?

Answer 23

Perl 6, 34 bytes

{+unique ~«(.base(2)~~m:ex/1.*/)}

Test it

Expanded:

{
  +                                # turn into Numeric (number of elements)
   unique                          # use only the unique ones
          ~«(                      # turn into strings
             .base(2)              # the input in base 2
                     ~~
                       m:ex/1.*/   # :exhaustive match substrings
                                )
}