17
\$\begingroup\$

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.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ Can you confirm 63->5 and not 6? Bin(63)=111111 -> six distinct nonzero substrings \$\endgroup\$
    – dylnan
    Jan 22, 2018 at 17:19
  • \$\begingroup\$ Related. (Uses subsequences instead of substrings and doesn't disregard leading zeros.) \$\endgroup\$ Jan 22, 2018 at 17:22
  • 1
    \$\begingroup\$ @dylnan Typo. Fixed. \$\endgroup\$
    – 0WJYxW9FMN
    Jan 22, 2018 at 17:24
  • \$\begingroup\$ @MartinEnder Is this different enough to stay on this site or shall I delete it as a duplicate? I think it's sufficiently different, but you know a lot better than I do. \$\endgroup\$
    – 0WJYxW9FMN
    Jan 22, 2018 at 17:26
  • \$\begingroup\$ @J843136028 The bigger difference for not making it a duplicate is the time restriction on the other challenge. You're fine. (Just posted the link, so that the challenges show up in each other's sidebar.) \$\endgroup\$ Jan 22, 2018 at 17:27

25 Answers 25

7
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ You can move the +1 from the range to bin(i) \$\endgroup\$
    – Rod
    Jan 22, 2018 at 17:50
  • 1
    \$\begingroup\$ In fact since we always count n itself and are to always exclude 0 from our count we can instead always exclude n and always count 0 (bin(n) starts '0b...'), hence we can remove the 1, and +1 entirely and leave bin(i) as is to save four bytes Try it online! \$\endgroup\$ Jan 22, 2018 at 18:11
5
\$\begingroup\$

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 N2 (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.

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

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Awwhh... I thought my filter was smart. bŒʒć}Ùg but nope, that's better. \$\endgroup\$ Jan 23, 2018 at 20:10
3
\$\begingroup\$

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

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

Try it online!

Takes input as a binary string.

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

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.

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

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.

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

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 [] []
\$\endgroup\$
3
  • \$\begingroup\$ Welcome to the site! Good to have more people golfing in Haskell! Some things pop out immediately in this answer as things that could be improved. First is that there is no space required before calling a function on a list. So r [] [] can just be r[][] and you can get rid of another space on the second line the same way. The other is that both your comparisons (/="") and (=='0') can be written as inequalities a little shorter. (/="") can always be (>""), because "" is the smallest string, and (=='0') can be written as (<'1') since your inputs can only be 1 or 0. \$\endgroup\$
    – Wheat Wizard
    Oct 4, 2020 at 13:40
  • \$\begingroup\$ @WheatWizard - thanks! Annoyingly, those inequality changes are confusing emacs haskell-mode for some reason. :( \$\endgroup\$
    – occipita
    Oct 4, 2020 at 13:49
  • \$\begingroup\$ Two more things I notice: (You can ask me to stop trying to help whenever) First is that in Haskell we allow point-free submissions. The rules are a little confusing but in short, you don't have to count the assignment (f=) on your function because it is point-free. The other is that [t:x|x<-o] could be map(t:)o which is a bit shorter. If you want some more tips we have a tips page just for Haskell which is especially good for beginners. \$\endgroup\$
    – Wheat Wizard
    Oct 4, 2020 at 13:59
1
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ You can accept a binary string as input, you can also replace set(...) with {...} and xrange with range \$\endgroup\$
    – Rod
    Jan 22, 2018 at 17:37
  • \$\begingroup\$ You can also move the +1 from the range to the slice, and switch the s.startswith to int(s,2) like this \$\endgroup\$
    – Rod
    Jan 22, 2018 at 17:42
  • 1
    \$\begingroup\$ If you want to keep your old approach, you can also use this for the same byte count \$\endgroup\$
    – Rod
    Jan 22, 2018 at 17:48
1
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You could actually use Jelly's Truthy Indexes atom, T, with ẆḄQTL \$\endgroup\$ Jan 22, 2018 at 17:46
1
\$\begingroup\$

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.

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

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.

\$\endgroup\$
4
  • \$\begingroup\$ You can roll the last three stages into one by using the q (or p) modifier in addition to w. You also don't need to specify C explicitly, because it's the default stage type if there is only a single source left. \$\endgroup\$ Jan 23, 2018 at 9:15
  • \$\begingroup\$ @MartinEnder Thanks, I'm still used to M being the default stage type! \$\endgroup\$
    – Neil
    Jan 23, 2018 at 9:53
  • \$\begingroup\$ Well, C kinda is what M used to be. :) \$\endgroup\$ Jan 23, 2018 at 9:53
  • \$\begingroup\$ I know why it's the default, it's just getting used to switching. \$\endgroup\$
    – Neil
    Jan 23, 2018 at 9:56
1
\$\begingroup\$

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!

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

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.

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

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!

\$\endgroup\$
2
  • \$\begingroup\$ What does ___ do? \$\endgroup\$
    – FrownyFrog
    Jan 23, 2018 at 20:07
  • \$\begingroup\$ Pattern matching, _ is a single item, __ is one or more, ___ is 0 or more. \$\endgroup\$ Jan 23, 2018 at 20:14
1
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 47 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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)

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to PPCG! Regarding your insertion of newlines for readability, it is usually preferred to have one scoring version which has exactly the amount of bytes as written in the header, and then an additional ungolfed or less-golfed version for readability. \$\endgroup\$
    – Laikoni
    Jan 22, 2018 at 23:42
  • \$\begingroup\$ @Laikoni Thanks for the heads-up! Will keep in mind for future posts! \$\endgroup\$
    – Nihilish
    Jan 22, 2018 at 23:46
  • \$\begingroup\$ String b=...,t and int i=...,j,k to save chars for repeated declarations of the same type. Your code also wouldn't qualify as an entry because it's a snippet, neither a full program nor a functional fragment, you have to write either a function or wrap your code in the lambda form \$\endgroup\$
    – Unihedron
    Jan 23, 2018 at 3:30
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

J, 34 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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?
\$\endgroup\$
0
\$\begingroup\$

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
                                )
}
\$\endgroup\$

Your Answer

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

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