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

Haskell (126121 bytes)

import Data.List
r o c(t:s)=r([t]:[t:x|x<-o])(o++c)s
r o c[]=o++c
f=length.nub.filter(>"").map(dropWhileEnd(<'1')).r[][]

(5 bytes improvement thanks to @WheatWizard's comment)

Defines a function "f" that accepts a binary string as input.

Ungolfed and commented:

import Data.List -- unfortunately we need some functions that aren't in Prelude

-- recursively generate all sublists of a given list (or string)
-- arguments are the list of sublists currently being worked with, 
--   a list of finished sublists, and list to examine
-- output is a list of reversed lists
rsubstrs :: [[t]]->[[t]]->[t]->[[t]]

rsubstrs open closed (t:ts) = rsubstrs ([t]:[t:o|o<-open]) (open++closed) ts
rsubstrs open closed [] = open++closed

-- count unique nonzero binary substrings, produced by composing a sequence of functions:
--   rsubstrs above (with two empty lists supplied to the first two curried arguments)
--   a map operation that removes any trailing sequences of zeros
--   filter to remove empty strings (which were zeros)
--   nub, which finds all unique items in a list
--   length, to count the results
countsubs = length . nub . filter (/="") . map (dropWhileEnd (=='0')) . rsubstrs [] []

Answer 9

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 10

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 11

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

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 14

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 15

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 16

Husk, 7 bytes

←LumḋQḋ

Try it online!

Explanation

←LumḋQḋ
      ḋ binary digits of the input
     Q  all possible sublists
   mḋ   convert each back to base-10
  u     uniquify
 L      get the length
←       decrement (since one of the sublists will be 0)

Answer 17

Perl 6, 47 bytes

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

Try it online!

Answer 18

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 19

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 20

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 21

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 22

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 23

J, 34 bytes

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

Try it online!

Answer 24

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 25

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