text:
Calculate Standard Deviation
Challenge
Given a list of numbers, calculate the population standard deviation of the list.
Use the following equation to calculate population standard deviation:

Input
The input will a list of integers in any format (list, string, etc.). Some examples:
56,54,89,87
67,54,86,67

The numbers will always be integers.
Input will be to STDIN or function arguments.
Output
The output must be a floating point number.
Rules
You may use built in functions to find the standard deviation.
Your answer can be either a full program or a function.
Examples
10035, 436844, 42463, 44774 => 175656.78441352615

45,67,32,98,11,3 => 32.530327730015607

1,1,1,1,1,1 => 0.0

Winning
The shortest program or function wins.
Leaderboard

var QUESTION_ID=60901,OVERRIDE_USER=30525;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

You mean the output must be a floating point OR integer?

I think most build-in standard deviation functions calculates the the sample standard deviation.

What about if input list is void?175656.78441352615 result to me 175656.78441352614

@RosLuP You don't have to worry about that

Does the code need to have some provision for taking input? For example, in Matlab you could do std(x), where x is the list of numbers. So do I need to have code that asks the user for input (prompt, etc)?

@a13a22 As per PPCG's standard rules, you are fine to take input via function arguments

Clip, 3
.sk

.s is the standard deviation, k parses the input in the form {1,2,3}.

What formula is used for the standard deviation? I could not find it int he reference.

@flawr It's this chart, towards the bottom.

@CᴏɴᴏʀO'Bʀɪᴇɴ I saw that, but there is no formula given.

@flawr Oh, I see. Perhaps then it is up to the interpreter, if such a thing exists.

@CᴏɴᴏʀO'Bʀɪᴇɴ I found it here on line 493, it seems to be ok!

@flawr That's great! Nice reference. Worries aside, this is a fantastic answer.

Mathematica, 24 22 bytes
Nice, Mathematica has a built-in StandardDevi... oh... that computes the sample standard deviation, not the population standard deviation.
But what if we use Variance... oh... same deal.
But there is yet another related built-in:
CentralMoment[#,2]^.5&

Yay. :)
This also works for 22 bytes:
Mean[(#-Mean@#)^2]^.5&

And this for 27:
N@RootMeanSquare[#-Mean@#]&

Octave, 14 bytes
g=@(a)std(a,1)

Try it on ideone.

You can save two bytes by removing g= since the function handle doesn't need a name to be a valid submission.

kdb+, 3 bytes
dev

One of the APL derviates had to have this as a built-in.
Test run
q)dev 56, 54, 89, 87
16.53028
q)f:dev
q)f 10035, 436844, 42463, 44774
175656.8
q)f 45,67,32,98,11,3
32.53033

Dyalog APL, 24 23 21 20 19 17 bytes
*∘.5∘M×⍨-M×M←+/÷≢

This defines an unnamed, monadic function train, which is equivalent to the following function.
{.5*⍨M(×⍨⍵)-M⍵×(M←{(+/⍵)÷≢⍵})⍵}

Try them online on TryAPL.
How it works
The code consists of several trains.
M←+/÷≢

This defines a monadic 3-train (fork) M that executes +/ (sum of all elements) and ≢ (length) for the right argument, then applies ÷ (division) to the results, returning the arithmetic mean of the input.
M×M

This is another fork that applies M to the right argument, repeats this a second time, and applies × (product) to the results, returning μ2.
×⍨-(M×M)

This is yet another fork that calculates the square of the arithmetic mean as explained before, applies ×⍨ (product with itself) to the right argument, and finally applies - (difference) to the results.
For input (x1, …, xN), this function returns (x1 - μ2, …, xN - μ2).
*∘.5∘M

This composed function is applies M to its right argument, then *∘.5. The latter uses right argument currying to apply map input a to a*0.5 (square root of a).
(*∘.5∘M)(×⍨-(M×M))

Finally, we have this monadic 2-train (atop), which applies the right function first, then the left to its result, calculating the standard deviation as follows.

R, 41 40 39 36 30 28 bytes
code
Thanks to beaker, Alex A. and MickyT for much bytes.
cat(sd(c(v=scan(),mean(v))))

old codes
v=scan();n=length(v);sd(v)/(n/(n-1))**0.5
m=scan();cat(sqrt(sum(mean((m-mean(m))^2))))
m=scan();cat(mean((m-mean(m))^2)^.5)

This should yield the population standard deviation.

I think this does not output the required result: http://stats.stackexchange.com/a/25961/43450

I don't know R, but would it be possible to augment the input array with the mean of the array? It seems that might be shorter.

@beaker I am not sure, I think it is not possible but I am no expert.

On this site we typically can't assume a REPL environment unless explicitly allowed by the question. Thus in this case you'll need to use cat to print to the console.

Also, R uses ^ for exponentiation, which is a byte shorter than **.

@AlexA. Thats true! I don't know how but I had some problems with ^ a while ago and totaly forgot it, thank you Alex.

You don't need to sum the mean since mean returns a scalar; sum has no effect. 36 bytes: x=scan();cat(mean((x-mean(x))^2)^.5)

@MickyT that doesn't seems to work, it says it can't find x

@AndréMuta apologies, when I tested it I had an X hanging around.

@AlexA. too much information, thanks for the edit.

The scan can be moved in, but there are no savings unfortunately cat(mean(((x=scan())-mean(x))^2)^.5) since it would need to be bracketed.

Well you taught me something new at least @MickyT. ;)

@AndréMuta I was talking about doing something like this: v <- c(v,mean(v)) (I think this is correct) and then taking the standard deviation of the updated list.

@beaker you are a genious.

@beaker very nice

CJam, 24 22 21 bytes
q~_,_@_:+d@/f-:mh\mq/

Thanks to @aditsu for golfing off 1 byte!
Try it online in the CJam interpreter.
How it works
q~                    e# Read all input and evaluate it.
  _,                  e# Copy the array and push its length.
    _@                e# Copy the length and rotate the array on top.
      _:+d            e# Copy the array and compute its sum. Cast to Double.
          @/          e# Rotate the length on top and divide the sum by it.
            f-        e# Subtract the result (μ) from the array's elements.
              :mh     e# Reduce by hypotenuse.
                      e# a b mh -> sqrt(a^2 + b^2)
                      e# sqrt(a^2 + b^2) c mh -> sqrt(sqrt(a^2 + b^2)^2 + c^2)
                      e#                           = sqrt(a^2 + b^2 + c^2)
                      e# ⋮
                 \mq/ e# Divide the result by the square root of the length.

I think you can convert just the length to double

@aditsu Of course. Thanks!

:mh is genius btw :)

Reduce by hypotenuse. isn't something you see every day.

Pyth, 20 19 17 13 bytes
@.O^R2-R.OQQ2

Thanks to @FryAmTheEggman for golfing off 4 bytes!
Try it online.
How it works
        .OQ    Compute the arithmetic mean of the input (Q).
      -R   Q   Subtract the arithmetic mean of all elements of Q.
   ^R2         Square each resulting difference.
 .O            Compute the arithmetic mean of the squared differences.
@           2  Apply square root.

I like how the decomposition of a Pyth program looks like a skewed parabola.

Julia, 26 19 bytes
x->std([x;mean(x)])

This creates an unnamed function that accepts an array and returns a float.
Ungolfed, I guess:
function f(x::Array{Int,1})
    # Return the sample standard deviation (denominator N-1) of
    # the input with the mean of the input appended to the end.
    # This corrects the denominator to N without affecting the
    # mean.
    std([x; mean(x)])
end

TI-BASIC, 7 bytes
stdDev(augment(Ans,{mean(Ans

I borrowed the algorithm to get population standard deviation from sample standard deviation from here.
The shortest solution I could find without augment( is 9 bytes:
stdDev(Ans√(1-1/dim(Ans

I agree with AndréMuta, this does not produce the required result, see here.

@AndréMuta @flawr TI's builtin stdDev( calculates the sample SD; stdDev(augment(Ans,{mean(Ans computes the population SD. That's on the page you linked to.

APL, 24 bytes
{.5*⍨+/(2*⍨⍵-+/⍵÷≢⍵)÷≢⍵}

A little different approach than Dennis' Dyalog APL solution. This should work with any APL implementation.
This creates an unnamed monadic function that computes the vector (x - µ)2 as 2*⍨⍵-+/⍵÷≢⍵, divides this by N (÷≢⍵), takes the sum of this vector using +/, and then takes the square root (.5*⍨).
Try it online

Not every APL implementation supports {dfns}, ⍨, or ≢. However, every version supports R←F Y R←(+/((Y-+/Y÷⍴Y)*2)÷⍴Y)*.5

Python 3.4+, 30 bytes
from statistics import*;pstdev

Imports the builtin function pstdev, e.g.
>>> pstdev([56,54,89,87])
16.53027525481654

I think just pstdev after the first line is ok? I believe xnor did that a while ago with sum. It sort of makes sense wrt how anonymous lambdas would be used i.e. p=pstdev or map(pstdev, [...])

I was going to say the same thing. Meta posts seem to support just putting a function literal.

I think you still need to write the literal pstdev though, like from statistics import*;pstdev. Otherwise, this could be any function from that library.

@xnor Edited. tbh I'm not really sure about the ruling on these situations...

Maybe a meta question would be helpful? :)

Haskell, 61 bytes
d n=1/sum(n>>[1])
f a=sqrt$d a*sum(map((^2).(-)(d a*sum a))a)

Straightforward, except maybe my custom length function sum(n>>[1]) to trick Haskell's strict type system.

You can use sum(1<$n) and <$> for map.

It just occurred to me that those functions might not be present because of an older GHC version at the time of this answer, but according to this tip they were introduced to prelude in March 2015, and the site policy has changed anyway to allow newer language features.

Jelly
11 bytes
S÷L
Ç²_²ÇN½

This is a direct translation of my APL answer to Jelly. Try it online!
How it works
S÷L        Helper link. Argument: z (vector)

S          Compute the sum of z.
  L        Compute the length of z.
 ÷         Divide the former by the latter.
           This computes the mean of z.

Ç²_²ÇN½    Main link. Argument: z (vector)

Ç          Apply the previous link, i.e., compute the mean of z.
 ²         Square the mean.
   ²       Square all number in z.
  _        Subtract each squared number from the squared mean.
    Ç      Take the mean of the resulting vector.
     N     Multiply it by -1.
      ½    Take the square root of the result.

J, 18 bytes
[:%:@M*:-M*M=:+/%#

This is a direct translation of my APL answer to J.
Try it online!

I had no idea M was a predefined built in.

It isn't. M=:+/%# is an inline function definition.

But it's predefined, right? Perhaps builtin is the wrong term

No, it's not predefined. M=:+/%# saves the verb +/%# in M, then calls it.

I am sorry XD I didn't see the last part

That link doesn't work anymore. Could you perhaps move it to https://tio.run/nexus/J ? I would, but I don't know enough about J to setup the input correctly/verify it still works.

@DJMcMayhem Done. Thanks for the heads-up.

Haha, no problem. I came across it here.

Yes, I saw. The post author gets a notification when an edit it suggested.

16 bytes

Prolog (SWI), 119 bytes
Code:
q(U,X,A):-A is(X-U)^2.
p(L):-sumlist(L,S),length(L,I),U is S/I,maplist(q(U),L,A),sumlist(A,B),C is sqrt(B/I),write(C).

Explanation:
q(U,X,A):-A is(X-U)^2.   % calc squared difference of X and U
p(L):-sumlist(L,S),      % sum input list
      length(L,I),       % length of input list
      U is S/I,          % set U to the mean value of input list
      maplist(q(U),L,A), % set A to the list of squared differences of input and mean
      sumlist(A,B),      % sum squared differences list
      C is sqrt(B/I),    % divide sum of squares by length of list
      write(C).          % print answer

Example:
p([10035, 436844, 42463, 44774]).
175656.78441352615

Try it out online here

Arn, 19 18 14 bytes
¯‡iʠØbmÅQƥªÈªÆ

Try it!
Explained
Unpacked: :/mean(n{:*n-mean:s}\
:/                      Square root
  mean                  Mean function
    (                   Begin expression
        n{              Block with key of n
          :*            Square
              n
            -           Subtraction
              mean
                    _   Variable initialized to STDIN; implied
                  :s    Split on spaces
         }              End of block
       \                Mapped over
         _              Implied
    )                   End of expression; Implied

I'm very intrigued by Arn as a cool new different language.  But am I getting it wrong or is the compression ('packing') quite inefficient?  The 'unpacked' code is only 21 characters, including 2x the word 'mean' (which surely must be a single-byte token (?)) and 1x parenthesis (which could be completely avoided by rearranging to RPN), so I would have guessed that the 'packed' code would be at most 14 characters long.  What am I missing?

Packing does not use that method of compression (mainly because most of the time you are NOT using a single word, but rather punctuation 90% of the time). Because of this, I essentially had two options for compression; pack the 7-bit characters into 8-bit characters (11% compression) or do something a bit stranger. The latter involves converting the ascii into a massive number (base 95) and then reading it off into a codepage, which results in approximately a 17% compression rate. Naturally, I chose option B here. That is why the compression doesn’t seem nearly as efficient as you thought.

Thanks for the explanation!  It's particularly interesting to hear other languages' strategies now that there's a new 'golf a golfing language' challenge!  Could you (or do you) at least reduce the text of 'mean' to 'M' (or 'ME' once you run-out of one-character function names) before doing the base95->256 compression, though?

I’ve considered shortening function names, but so far I haven’t. If a user wanted to shorten it manually, they could do this: m(_):=.mean

However, what you suggested is a good idea, and so I’ll test it out a bit

Cool.  You wouldn't actually need to shorten the names in the unpacked code: the 'packing' could first shorten names, and then base-95->256 compress.  Then you'd have the win-win situation of a golfy language that's actually readable (at least, before packing)!

When will there be an Arn manual page or 'how-to'?

There is one, it can be found here. If anything isn't clear just let me know.

Brachylog, 16 bytes
⟨∋-⟨+/l⟩⟩ᶠ^₂ᵐ↰₂√

Try it online! (all cases at once)
I feel like maybe there's some shorter way to compute the squared deviations than 13 bytes.

Haskell, 45 bytes
(?)i=sum.map(^i)
f l=sqrt$2?l/0?l-(1?l/0?l)^2

Try it online!
The value i?l is the sum of the i'th powers of elements in l, so that 0?l is the length and 1?l is the sum.

05AB1E, 10 7 bytes
ÅA-nÅAt

-3 bytes thanks to @ovs.
Try it online or verify all test cases.
Explanation:
ÅA       # Get the arithmetic mean of the (implicit) input-list
  -      # Subtract it from each value in the (implicit) input-list
   n     # Square each of those
    ÅA   # Take the arithmetic mean of that
      t  # And take the square-root of that
         # (after which it is output implicitly as result)

Just found this challenge, ÅA-nÅAt is a more literal implementation of the given formula at 7 bytes. (This scores about 404 points in the other challenge)

JavaScript (ES6), 73 bytes
a=>Math.sqrt(a.reduce((b,c)=>b+(d=c-eval(a.join`+`)/(l=a.length))*d,0)/l)

@BetaDecay Regarding precision of the output? My original actually didn't have that correct, and I fixed it right after, only to discover floating point was ok hehe... So is it good now as it is?

Yeah that's fine :)

Psst... you can shave off 5 bytes by using this summing method eval(a.join\+`)instead of a.reduce((e,f)=>e+f)`

@GeorgeReith Nice trick! I'm going to have to remember that one for later...

@StevenPenny It seems to work for me.

@TheFourthMarshal this answer is using the naive algorithm https://wikipedia.org/wiki/Algorithms_for_calculating_variance#Na%C3%AFve_algorithm - so it wont really be useful outside the scope of this answer

Simplex v.0.5, 43 bytes
Just 'cuz. I really need to golf this one more byte.
t[@u@RvR]lR1RD@wA@T@{j@@SR2ERpR}u@vR@TR1UEo
t[      ]                                     ~~ Applies inner function to entire strip (left-to-right)
  @                                           ~~ Copies current value to register
   u                                          ~~ Goes up a strip level
    @                                         ~~ Dumps the register on the current byte
     R                                        ~~ Proceeds right (s1)
      v                                       ~~ Goes back down
       R                                      ~~ Proceeds right (s0)
                                              ~~ Go right until an empty byte is found
         lR1RD                                ~~ Push length, 1, and divide.
              @                               ~~ Store result in register (1/N)
               wA                             ~~ Applies A (add) to each byte, (right-to-left)
                 @T@                          ~~ Puts 1/N down, multiplies it, and copies it to the register
                    {          }              ~~ Repeats until a zero-byte is met
                     j@@                      ~~ inserts a new byte and places register on it
                        SR                    ~~ Subtract it from the current byte and moves right
                          2E                  ~~ Squares result
                            RpR               ~~ Moves to the recently-created cell, deletes it, and continues
                                u@v           ~~ takes 1/N again into register
                                   R@T        ~~ multiplies it by the new sum
                                      R1UE    ~~ takes the square root of previous
                                          o   ~~ output as number

Perl5, 39 38

 16 for the script
+22 for the M switch
+ 1 for the E switch
=39
perl -MStatistics::Lite=:all -E"say stddevp@ARGV" .1 .2 300

Tested in Strawberry 5.20.2.

Oh, but then I realized that you said our answers can be functions instead of programs. In that case,
{use Statistics::Lite":all";stddevp@_}

has just 38. Tested in Strawberry 5.20.2 as
print sub{use Statistics::Lite":all";stddevp@_}->( .1, .2, 300)

MathGolf, 10 7 bytes
ë_▓-²▓√

Port of my 05AB1E answer.
Try it online.
Explanation:
ë        # Read all inputs as float-list
 _       # Duplicate that list
  ▓      # Get the average of that list
   -     # Subtract that average from each value in the list
    ²    # Square each value
     ▓   # Take the average of that again
      √  # And take the square root of that
         # (after which the entire stack joined together is output implicitly as result)

Whispers v2, 105 bytes
> Input
>> #1
>> ∑1
>> 3÷2
>> L-4
>> L²
>> Each 5 1
>> Each 6 7
>> ∑8
>> 9÷2
>> √10
>> Output 11

Try it online!
In the latest version of Whispers, the builtin σ can be used to shave off around 70 bytes.
How it works
For those unfamiliar with Whispers, the language works by using numbers as line references in order to pass values between lines. For example, the line >> 3÷2 doesn't calculate \$3 \div 2\$, rather it takes the values of lines 3 and 2 and calculates their division. Execution always begins on the last line.
This program simply implements the standard formula for standard deviation:
$$\sigma = \sqrt{\frac{1}{N}\sum^N_{i=1}{(x_i-\bar{x})^2}}$$
$$\bar{x} = \frac{1}{N}\sum^N_{i=1}{x_i}$$
Lines 2, 3 and 4 define \$\bar{x}\$, with it's specific value accessible on line 4. Line 2 stores \$N\$. We then calculate \$(x_i-\bar{x})^2\$ for each \$x_i \in x\$ with the lines 5, 6, 7 and 8:
>> L-4
>> L²
>> Each 5 1
>> Each 6 7

Line 7 runs line 5 over each element in the input, which takes the difference between each element in the input and the mean, We then square these differences using lines 8 and 6. Finally, we take the sum of these squares (line 9), divide by \$N\$ (line 10) and take the square root (line 11). Finally, we output this result.

Shasta v0.0.10, 65 bytes
{(**(/(sum(map${|x|(**(- x(/(sum$)(length$)))2)}))(length$)).5)}

Online interpreter not set up yet, tested on my machine
Explanation:
{...} Function taking argument $
(** ... .5) Square root of
(/ ... (length $)) Dividing ... by the length of $
(sum ...) The sum of
(map $ {|x| ...}) Mapping each x in $ to
(** ... 2) The square of
(- x ...) The difference between x and
(/ (sum $) (length $)) The mean of $

Python, 57 bytes
lambda l:(sum((x-sum(l)/len(l))**2for x in l)/len(l))**.5

Takes input as a list
Thanks @xnor

I think you can do .5 in place of 0.5 to save a byte. Also do you mean len(x) instead of len(l)?

@AlexA. Uhh, no I don't think so...

Sorry, got confused. Disregard the x and l nonsense. But you can still do .5 to save a byte.

@BetaDecay It's shorter to use a list-comp than to map a lambda: sum((x-sum(l)/len(l))**2for x in l).

A different formulation gave the same length: lambda l:(sum(x*x*len(l)for x in l)-sum(l)**2)**.5/len(l).

PowerShell, 122
:\>type stddev.ps1
$y=0;$z=$args -split",";$a=($z|?{$_});$c=$a.Count;$a|%{$y+=$_};$b=$y/$c;$a|%{$x+
=(($_-$b)*($_-$b))/$c};[math]::pow($x,0.5)

explanation
<#
$y=0                            init
$z=$args -split","              split delim ,
$a=($z|? {$_})                  remove empty items
$c=$a.Count                     count items
$a|%{$y+=$_}                    sum
$b=$y/$c                        average
$a|%{$x+=(($_-$b)*($_-$b))/$c}  sum of squares/count
[math]::pow($x,0.5)             result
#>

result
:\>powershell -nologo -f stddev.ps1 45,67,32,98,11,3
32.5303277300156

:\>powershell -nologo -f stddev.ps1 45,  67,32,98,11,3
32.5303277300156

:\>powershell -nologo -f stddev.ps1 45,  67,32, 98 ,11,3
32.5303277300156

:\>powershell -nologo -f stddev.ps1 10035, 436844, 42463, 44774
175656.784413526

:\>powershell -nologo -f stddev.ps1 1,1,1,1,1,1
0

Fortran, 138 bytes
Just a straightforward implementation of the equation in Fortran:
double precision function std(x)
integer,dimension(:),intent(in) :: x
std = norm2(dble(x-sum(x)/size(x)))/sqrt(dble(size(x)))
end function

SmileBASIC, 105 bytes (as a function)
I just noticed it's allowed to be a function. Whoops, that reduces my answer dramatically. This defines a function S which takes an array and returns the population standard deviation. Go read the other one for an explanation, but skip the parsing part. I don't want to do it again.
DEF S(L)N=LEN(L)FOR I=0TO N-1U=U+L[I]NEXT
U=1/N*U FOR I=0TO N-1T=T+POW(L[I]-U,2)NEXT RETURN SQR(1/N*T)END

As a program, 212 bytes
Unfortunately, I have to take the input list as a string and parse it myself. This adds over 100 bytes to the answer, so if some input format other than a comma-separated list is allowed I'd be glad to hear it. Also note that because VAL is buggy, having a space before the comma or trailing the string breaks the program. After the comma or at the start of the string is fine.
DIM L[0]LINPUT L$@L I=INSTR(O,L$,",")IF I>-1THEN PUSH L,VAL(MID$(L$,O,I-O))O=I+1GOTO@L ELSE PUSH L,VAL(MID$(L$,O,LEN(L$)-O))
N=LEN(L)FOR I=0TO N-1U=U+L[I]NEXT
U=1/N*U FOR I=0TO N-1T=T+POW(L[I]-U,2)NEXT?SQR(1/N*T)

Ungolfed and explained:
DIM L[0]  'define our array
LINPUT L$ 'grab string from input

'parse list
'could've used something cleaner, like a REPEAT, but this was shorter
@L
I=INSTR(O,L$,",")                 'find next comma
IF I>-1 THEN                      'we have a comma
 PUSH L,VAL(MID$(L$,O,I-O))       'get substring of number, parse & store
 O=I+1                            'set next search location
 GOTO @L                          'go again
ELSE                              'we don't have a comma
 PUSH L,VAL(MID$(L$,O,LEN(L$)-O)) 'eat rest of string, parse & store
ENDIF                             'end

N=LEN(L) 'how many numbers we have

'find U
'sum all of the numbers, mult by 1/N
FOR I=0 TO N-1
 U=U+L[I]
NEXT
U=1/N*U

'calculate our popstdev
'sum(pow(x-u,2))
FOR I=0 TO N-1
 T=T+POW(L[I]-U,2)
NEXT
PRINT SQR(1/N*T) 'sqrt(1/n*sum)

Axiom, 137 bytes
m(a:List Float):Complex Float==(#a=0=>%i;reduce(+,a)/#a)
s(a:List Float):Complex Float==(#a=0=>%i;n:=m(a);sqrt(m([(x-n)^2 for x in a])))

The function m() would return the mean of the list in input. Both the functions on error return %i the imaginary constant sqrt(-1).
Code for test and results. [but the result if it is ok, it is the real part of one complex number]
(6) -> s([45,67,32,98,11,3])
   (6)  32.5303277300 15604966

(7) -> s([10035,436844,42463,44774])
   (7)  175656.7844135261 4035

(8) -> s([1,1,1,1,1,1])
   (8)  0.0

Python 3, 49 bytes
lambda l,N:(sum((i-sum(l)/N)**2for i in l)/N)**.5

Try it online!
Takes in l, a list of integers, and N, the number of integers present.

Pyt, 13 bytes
←Đ↔Ł↔Đµ-²Ʃ⇹/√

Implements the formula for standard deviation

Scala, 80 bytes
Golfed version. Try it online!
l=>{val s=(0 to 2).map(i=>l.map(pow(_,i)).sum);sqrt(s(2)/s(0)-pow(s(1)/s(0),2))}

Ungolfed version. Try it online!
object Main {

  def powerSum(i: Int, list: List[Int]): Double =
    list.map(scala.math.pow(_, i)).sum

  def f(l: List[Int]): Double = {
    val sum0 = powerSum(0, l)
    val sum1 = powerSum(1, l)
    val sum2 = powerSum(2, l)

    scala.math.sqrt(sum2 / sum0 - scala.math.pow(sum1 / sum0, 2))
  }

  def main(args: Array[String]): Unit = {
    println(f(List(45, 67, 32, 98, 11, 3)))
  }

}


text:
Zzub Zzif (reverse Fizz Buzz)
Given a snippet of fizz buzz output with all numbers removed, fill in the correct numbers with the lowest possible values such that the fizz buzz snippet is correct.  For the purposes of this challenge, fizz and buzz have their usual values of 3 and 5, respectively.
If the input is an invalid sequence of fizz, buzz and empty lines, then instead output just zzubzzif (with or without newlines).
Input and output may be newline separated lines, or whatever array-of-strings format is convenient to your language.
You may ignore or do whatever you like with capitalisation.
You will need to choose to handle one or more of these: fizzbuzz, fizz buzz, buzz fizz, etc, but you must choose at least one of these formats.
You may assume that all input is some sequence of fizz, buzz and empty lines.
Examples

Input:

fizz

Output:

2
fizz
4

Input:

buzz
fizz

Output:

buzz
fizz
7

Input:

fizzbuzz

Output:

13
14
fizzbuzz
16
17

Input:

Output:

1

Input:

fizz
fizz

Output:

zzubzzif

Input:

Output:

zzubzzif

Related.

Java, 205 bytes
s->{o:for(int i=0,j,h=s.length;++i<16;){for(j=h;j-->0;)if(s[j].contains("fizz")^(i+j)%3<1||s[j].contains("buzz")^(i+j)%5<1)continue o;String z=i+"";for(j=1;j<h;)z+="\n"+(i+j++);return z;}return"zzubzzif";}

Takes a String[] as input and returns a String.
Expanded, runnable code:
public class C {

    static final java.util.function.Function<String[], String> f = s -> {
        o:
        for (int i = 0, j, h = s.length; ++i < 16;) {
            for (j = h; j --> 0;) {
                if (s[j].contains("fizz") ^ (i + j) % 3 < 1 ||
                    s[j].contains("buzz") ^ (i + j) % 5 < 1) {
                    continue o;
                }
            }
            String z = i + "";
            for (j = 1; j < h;) {
                z += "\n" + (i + j++);
            }
            return z;
        }
        return "zzubzzif";
    };

    public static void main(String[] args) {
        System.out.print(f.apply(new String[]{"fizz", "", "buzz"}));
    }
}

s/fizz/f, s/buzz/b

C#, 212 bytes
I did the unthinkable.  I used a goto statement to break out of a loop!
string[]R(string[]a){for(int i,l=a.Length,n=0;n++<15;){for(i=l;i-->0;)if(((n+i)%3<1?"fizz":"")+((n+i)%5<1?"buzz":"")!=a[i])goto z;for(i=l;i-->0;)a[i]=a[i]==""?""+(n+i):a[i];return a;z:;}return new[]{"zzubzzif"};}

This takes advantage of the fact that the sequence must start within the first 15 elements.
Indentation and new lines for readability:
string[]R(string[]a){
    for(int i,l=a.Length,n=0;n++<15;){
        for(i=l;i-->0;)
            if(((n+i)%3<1?"fizz":"")+((n+i)%5<1?"buzz":"")!=a[i])
                goto z;
        for(i=l;i-->0;)
            a[i]=a[i]==""?""+(n+i):a[i];
        return a;
    z:;
    }
    return new[]{"zzubzzif"};
}

does C# not have a break keyword?

@cat, it does, but the goto jumps out of the inner loop and over the rest of the outer loop's logic.

First time I heard about goto on C#! Didn't  even know C# had it!

CJam, 72 bytes
"zzubzzif":MaqN/:Q,_F+{)_[Z5]f%:!MW%4/.*s\e|}%ew{:sQ1$A,sff&:s.e|=}=N*o;

The program will exit with an error if it has to print zzubzzif.
Using the Java interpreter, STDERR can be closed to suppress an eventual error message. If you try the program in the CJam interpreter, ignore all output after the first line.
How it works
"zzubzzif" e# Push that string.
:Ma        e# Save it in M and wrap in in an array.
qN/:Q      e# Split the input into lines and save in Q.
,_F+       e# Count the lines and add 15 to a copy of the result.
{          e# For each integer I between 0 and lines+14:
  )_       e#   Increment I and push a copy.
  [Z5]     e#   Push [3 5].
  f%       e#   Map % to push [(I+1)%3 (I+1)%5].
  :!       e#   Apply logical NOT to each remainder.
  MW%4/    e#   Push ["fizz" "buzz"].
  .*       e#   Vectorized string repetition.
  s\       e#   Flatten the result and swap it with I+1.
  e|       e#   Logical OR; if `s' pushed an empty string, replace it with I+1.
}%         e#
ew         e# Push the overlapping slices of length "lines".
{          e# Find; for each slice:
  :s       e#   Cast its elements to string (e.g., 1 -> "1").
  Q1$      e#   Push the input and a copy of the slice.
  A,s      e#   Push "0123456789".
  ff&      e#   Intersect the slice's strings' characters with that string.
  :s       e#   Cast the results to string. This replaces "fizz", "buzz"
           e#   and "fizzbuzz" with empty strings.
  .e|      e#   Vectorized logical OR; replace empty lines of the input
           e#   with the corresponding elements of the slice.
  =        e#   Check the original slice and the modified input for equality.
}=         e# Push the first match or nothing.
           e# We now have ["zzubzzif"] and possibly a solution on the stack.
N*         e# Join the topmost stack item, separating by linefeeds.
o          e# Print the result.
;          e# Discard the remaining stack item, if any.

Python, 176 Bytes
Could probably do a lot better, but first attempt at Golf.  Tips appreciated :)
Shrunk
def f(a):l=len(a);g=lambda n:'fizz'*(n%3<1)+'buzz'*(n%5<1);r=range;return next(([g(x)or x for x in r(i%15,i%15+l)]for i in r(1,16)if all(g(i+x)==a[x]for x in r(l))),g(0)[::-1])

Original
def f(a):
  l = len(a)
  g = lambda n: 'fizz'*(n%3<1)+'buzz'*(n%5<1)
  r = range
  return next(
    (
      [g(x) or x for x in r(i % 15,i % 15 + l)]
      for i in r(1,16)
      if all(
        g(i + x) == a[x] for x in r(l)
      )
    ),
    g(0)[::-1]
  )

Welcome to PPCG! Standard formatting guidelines are to preface your answer with a header, so readers know the language and leaderboard snippets can properly parse your answer. For example, #Java, 205 Bytes as the first line of your answer.

Try replacing the lambda with the following:
'fizz'*(n%3<1)+'buzz'*(n%5<1)
You can remove the f and b assignments then. (f+b)[::-1] can then be a call to a known 'fizzbuzz' e.g. g(15)[::-1].

Thanks for the suggestion! Down to 183! I think g(0) also works to save another byte :)

python 2 allows to remove some spaces before keywords when there is no ambiguity : for example ..] for  may be written ..]for. Applying this trick, you get 177 chars

Could you include the input you assumed when you wrote the code next time. e.g. list of the form  ['','fizz',''] There are also a few more to remove if you compare the input list vs a list comp rather than using all() if a==[g(i + x) for x in r(l)]

Perl, 140 bytes
$f=fizz;$b=buzz;@a=<>;@x=map{s!\d!!gr.$/}@s=map{$_%15?$_%3?$_%5?$_:$b:$f:$f.$b}(++$c..$c+$#a)while$c<15&&"@x"ne"@a";print$c<15?"@s":zzubzzif

Explanation

@a is the array of input lines
Inside the while loop,
@s has the generated fizz-buzz sequence
@x is the same as @s but with numbers replaced with empty strings and a new line appened to every element (to match with @a)
$c is a counter from 1 to 15
The loop runs till @x becomes the same as the input @a
Outside the loop, the output is @s or zzufzzib based on whether $c was in its limits or not

JavaScript (Node.js), 127 bytes
f=(n,j=1)=>j<99?(M=n.map((e,i)=>e?e:j+i)).some((e,i)=>e!=((J=j+i)%3?J%5?J:'buzz':'fizz'+(J%5?'':'buzz')))?f(n,j+1):M:'zzubzzif'

Try it online!
I came across this challenge by accident after clicking on one of the answerers' profiles. Expects an array of lowercase strings.
How?
FizzBuzz loops every 15 lines, which means that we can reasonably expect that by the time the start counter reaches 99, we will have looped through fizzbuzz a few times, hence allowing us to stop the recursion and instead output "zzubzzif".
If the counter is still less than 99, then we first fill in the falsy lines (empty strings) with their numbers, and check if it makes a valid FizzBuzz snippet using some. If one doesn't fit in, then recall the function with j+1. Otherwise return M.

e?e:j+i => e||j+i

Python 2, 173 bytes
import re
def f(u,i=0,s=""):
 exec"s+=`i%3/2*'Fizz'+i%5/4*'Buzz'or-~i`+' ';i+=1;"*100;s=s.replace("'","");return re.findall(' '.join(['\d+'if not x else x for x in u]),s)[0]

Try it online!

Vyxal, 200 bitsv2, 25 bytes
L:↵ƛ₍₃₅kF½ɽ*∑∴;l'vSǍ?⁼;h:[|kF⇩Ṙ

Try it Online!
Modern golfing languages with fractional byte encodings amiright.
I got this down from 27.something bytes to 25 bytes in drafts through a lot of fiddling with element ordering.
Explained
L:↵ƛ₍₃₅kF½ɽ*∑∴;l'vSǍ?⁼;h:[|kF⇩Ṙ
L:↵ƛ₍₃₅kF½ɽ*∑∴;                   # Generate fizzbuzz for the first (10 ** len(input)) numbers using the standard fizzbuzz approach.
               l                  # in windows of len(input)
                '                 # filtered to keep only
                 vSǍ              #   windows where all converted to string with digits removed
                    ?⁼            #   exactly equals the input
                       h:[|kF⇩Ṙ   # if that's an empty list, return the string "zzibzzuf", else the first item.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Find a multiple of a given number whose decimal representation looks like binary
I have come across a question on the Code Review site that seems interesting. I think OP is doing it wrong, but cannot be sure... So let's solve it for him! (write a program, not a function/procedure)
Input (stdin or similar):
An integer x in decimal notation. It is greater than 1 and less than 2^31.
Output (stdout or similar):
An integer y in decimal notation. The product x * y in decimal representation must contain only digits 0 and 1. It must be the minimal such number greater than 0.
Note: output is not limited - if the minimal y is around 10^100, your program must output all of its 100 digits (I don't know whether there is a reasonable limit, like 2^64, on y - didn't solve it).
Your program should finish in a reasonable time (1 second? 1 hour? - something like that) for all x in range.
Bonus:
If your program doesn't have a limit on the size of the input (except RAM), and has polynomial complexity, multiply the byte count of your program by 0.8 and round down.

Example: Input 2; output 5, because 2 * 5 = 10
Example: Input 21; output 481, because 21 * 481 = 10101

Disclaimer: I am not responsible for the question on the Code Review site. In case of any discrepancy, only the description above should be regarded as proper spec.
OEIS A079339

It should always be solvable. Clearly there must exist at least one q such that there are an infinite number of n such that 10^n mod x = q. Take x such values of n and add together the respective powers 10^n.

Multiples of 9 seem to produce unusually high results.

Related Project Euler problem, for anyone else who thought this question looked familiar

By polynomial complexity, do you mean polynomial in the number of digits of the input, or polynomial in the value of the input?

@RetoKoradi Polynomial in the number of digits, of course! Otherwise, you cannot run it => no fun.

input();print 0 - you should probably limit y to > 0 ;)

@SuperJedi224 well, you need at least 9 1's to get a multiple of 9

I guess I was too optimistic about complexity, and it's impossible to make it polynomial on the size of input - the size of the output seems to be exponential on input. But hey - all the 16 answers so far are brute-force?! Surely you can do better!

Umm... there is always a value that can be resolved that looks like binary (circumventing the output 0 rule), simply because there is an infinite range of numbers.

@anatolyg mine is not brute force

@primo re bounty: time to calc or time to print in console? Maybe redirect to file

@edc65 Output must be generated, although for timing it will be discarded (i.e. piped to /dev/null. I will however check it for accuracy). You may optimize your solution to produce each value sequentially, if that helps. If you prefer to be timed with a specific interpreter/compiler, please specify.

@primo, how special-cased can the fast code be? E.g. can it restrict to using narrower int types which wouldn't be sufficient for input 99999999?

@PeterTaylor if it produces the correct output for all values between 1-10000, I will consider it valid. I will be evaluating all solutions shortly.

I've a proof that the length of the output is indeed at most linear in the size of the input (and thus exponential in the length of the input), but it cannot fit in a comment box. It relies on two ideas: 1) That for any N, 10^i % N has a period with length <= N - 1 or has finite support, and 2) There exists a multiple of N that equals a linear combination of numbers less than N such that their coefficients sum to at most N.

The Bounty was awarded to aditsu's c answer. Final scoreboard: http://codepad.org/DVRGITHP (average of 5 runs). I didn't test any "count by one" solutions, so if I've missed yours, and it's faster than aditsu's c, I'll double down on the bounty.

I'm like 95% certain that the length of the output is linear in the length of the input; I'm trying to find an existence proof and possibly a constructive proof if I can get that far.

@Candles If you can prove that the worst case is repeated 9's (empirically correct up to quite a few repeated 9's), there's your constructive proof.

@SuperJedi224 multiples of mine that fit this answer will be at minimum 111111111, because any number x where x % 9 = 0, the numbers added up recursively will equal 9

Pyth, 8 bytes
fq`;{`*Q

Try it here.

How?

fq`;{`*Q   - Full program.

f          - First input where the condition is truthy over [1, ∞)
      *Q   - The product of the input and the current number
     `     - Converted to String.
    {      - Deduplicated.
 q         - Is equal to?
  `;       - The string representation of the innermost lambda variable, T, which is "10".
           - Output implicitly.

This pretty much relies on the fact that numbers do not have trailing zeros, and 1 always occurs before 0 in a positive integer only consisting of 0s and 1s.

Python 2, efficient solution, 99
n=input()
d={n:0}
k=1
while min(d):[d.setdefault((x+k)%n,d[x]+k)for x in set(d)];k*=10
print d[0]/n

Thanks Sp3000 for some golfing tips.
I challenge everybody else to post (in their own answers) how long it takes to get the result for input 72 or 99 :) If those are really fast, try something like 79992 next (still <1 sec here).
Explanation:
I thought this wasn't necessary (since the code is fairly readable), but I got a request, so here it goes:
The first idea is that a binary-looking number is a sum of 1 or more different powers of 10. Therefore, we can try to add various powers of 10 in different ways until we get remainder 0.
If we do that naively, it's the same as generating all binary-looking numbers and testing them. But a lot of remainders will be the same. A better way is to record only the smallest number that gave a certain remainder, and successively add greater powers of 10 to numbers we recorded. That's what the program does.
d is a dictionary/map where keys are remainders and values are binary-looking numbers with that remainder. The initial n:0 is a special case: it's supposed to be 0:0 so we can start adding powers to it, but the algorithm stops when finding key 0, so I used n instead, which is guaranteed to have the same effect and not interfere with the other values.
Then we start adding powers of 10 (stored in k) to all existing numbers and recording the remainders. We add k to the remainder: (x+k)%n and to the number: d[x]+k, and record it only if it's a new remainder: d.setdefault(…), then go to the next power: k*=10 and repeat until we get key 0: while min(d)
At the end, d[0] gives the binary-looking number that has remainder 0 mod n, so we divide it by n to get the solution.
Note: the program can be made more efficient by avoiding large numbers (recording exponents rather than powers of 10, and calculating remainders of powers from previous values), but it's code golf, so...
In fact, here, I wrote a faster version:
n=input()
d={n:0}
k=1
b=0
while 0not in d:
 for x in list(d):d.setdefault((x+k)%n,b)
 k=(k*10)%n;b+=1
x=10**d[0]
while x%n:x+=10**d[n-x%n]
print x/n

My answer doesn't get either. xD "Dangit, Java, curse thy choice of Integer.MAX_VALUE over using BigInteger by default!" - Every Java Programmer Ever

@VTCAKAVSMoACE why don't you use Long?

Hmm. It's an extra byte, but... worth it. Thanks!

Or not. That actually seriously reduces it. Thanks!

72, 99 and some more in ~370 millisec http://codegolf.stackexchange.com/a/61051/21348

Timings for solving 99: aditsu: 0.001 seconds; xnor: 5+ hours and it still didn't complete.

@aditsu challenge accepted!, well almost :) [72 = ~0.007 s, 99 = ~0.45s] http://codegolf.stackexchange.com/a/61076/46177

You can get a speed-up of about 30% with some basic number theory. If ntlog(b, x) gives the greatest a such that x % (b**a) == 0 then start k at 10**max(ntlog(2,n), ntlog(5,n)).

@PeterTaylor what's ntlog?

Read the first half of that sentence again

@PeterTaylor is it just a weird name you gave to an ad-hoc function?

I have a vague memory of seeing it called the number-theoretic logarithm to base b somewhere, but I can't find a reference.

Javascript, 43 bytes
This ended up way shorter than I thought. It basically increments y up 1 until y * (input number) = (binary-looking number). Obviously quite inefficient.

for(x=prompt(y=0);!+('0b'+x*++y););alert(y)

Javascript (more efficient solution), 53 bytes
This one increments y in binary until y / (input number) = (number without a remainder). Then it outputs (number without a remainder).

for(x=prompt(y=1);(z=y.toString(2))%x;y++);alert(z/x)

Javascript (even more efficient solution), 76 bytes
This one combines both of the previous methods described above. It checks increments y until either y * (input number) = (binary-looking number) (meaning that the output is y) OR y / (input number) = (number without a remainder) (meaning that the output is (number without a remainder)).

for(x=prompt(y=a=0);!a;a=+('0b'+x*++y)?y:(z=y.toString(2))%x?0:z/x);alert(a)

It should give 1 when possible (example input: 1)

@edc65 Fixed - with no change in byte count!

This crashes Safari 9.0. Jussayin'. :)

But it's limited to small numbers in output. Javascript numbers have 17 digits of precision, OP is asking for something bigger (and it can be done using modular arithmetic)

Protip: Don't try input 72. Firefox 41 freezes up for 15 minutes and then crashes. I discovered this the hard way.

I added a more efficient solution, so no more crashes (I hope).

Python 2, 47 bytes
n=a=input()
while'1'<max(str(a)):a+=n
print a/n

Tracks the input number n and the current multiple a. When a looks like binary, output the ratio a/n. To check that a number is made of 0's and 1's, we compare the maximum char in its string representation to '1'.
Uses str(a) instead of `a` to avoid longs ending in L. Unfortunately, 'L' is bigger than '1'.

Perl, 27 bytes
#!perl -p
1while($_*++$\)=~/[2-9]/}{

Counting the shebang as one, input is taken from stdin.
Sample Usage
$ echo 2 | perl dec-bin.pl
5

$ echo 21 | perl dec-bin.pl
481

$ echo 98 | perl dec-bin.pl
112245

Perl, 25 bytes
#!perl -p
eval'0b'.++$\*$_||redo}{

A two byte improvement by @skmrx.
Rather than checking against a regex, this instead attempts to evaluate the product as a binary literal. Upon failure, it moves on to the next. Typically the oct function would be used for this purpose, but it silently trims invalid digits, which isn't useful in this challenge.

Perl, 40 bytes
#!perl -p
1while($b=sprintf"%b",++$i)%$_;$_=$b/$_

A far more efficient solution. We iterate over binary representations, interpret them as base 10, and then check for divisibility. Runtimes for all values under 100 are negligible.
Sample Usage
$ echo 72|perl dec-bin.pl
1543209875

$ echo 99|perl dec-bin.pl
1122334455667789

Nice :) I learnt a couple of  new things from your post today! While reading through your code, I found a way to shave off a couple of bytes from the first code:
eval"0b".$_*++$\||redo}{

But I guess we'll need to include use bigint to support the large numbers that OP has mandated to be supported :(

@skmrn That's brilliant. I had tried oct'0b'.++$\*$_, but it silently trims invalid digits. I didn't think to use eval instead.

Haskell, 72 70 64 60 58 bytes
main=do x<-readLn;print$[y|y<-[1..],all(<'2')$show$x*y]!!0

Edit: @Jan Dvorak helped me saving 4 bytes.
Edit: @BlackCap saved 2 bytes by switching to do notation. Thanks!

main=print.f=<<readLn

You can save a byte by inlining f: main=readLn>>= \x->print$[y|y<-[1..],all(<'2')$show$x*y]!!0

2 actually main=do x<-readLn;print$[y|y<-[1..],all(<'2')$show$x*y]!!0

@BlackCap: Nice! Thanks a lot!

Pyth, 9 bytes
f!-`*TQ10

Demonstration
For each multiple, convert to a string, subtract out the digits in 10 (using Pyth's handy int to str cast in this case) and then logically negate the result, terminating the seach only when the correct multiple is found.
Bonus solution, 10 bytes:
f.xi`*TQ2Z

This solution actually checks if the string representation of the number can be treated as a binary number (i ... 2) and terminates when an error is not thrown on this attempt.

Python 2, 67 65 63 60 bytes
a=input();b=1
while set(`a*b`)&set('23456789'):b+=1
print b

Thanks to Status for 2 bytes and Shebang for 5 bytes!

I think you must initialize b=1

Corrected, @anatolyg.

You can shave 2 bytes by doing any(c in`a*b`for c in'23456789')

Excellent, @Status, thanks.

I'm not sure about this but would not c in\a*b`for c in'10'` work?

Alas, syntax error, @Cole. It feels like you're onto something good, though.

You can save 6 bytes by changing your while condition to set('a*b')&set('23456789').

Implemented your suggestion @ThomasKwa, thanks!

\`` produces an Lfor longs and'L'>'1'`.

As @Clearquestionwithexamples said, this wont work for x*y > 2147483647.

Thanks @Clearquestionwithexamples; I've updated the answer with your solution.

@mbomb007 Now that he's changed to the set thing, he can use backticks.

I was going to post an answer, but it's close enough I'll just share the improvement. while set(str(n*i))-{"1","0"} or while set(str(n*i))-set("01") is shorter by 4 bytes.

JavaScript (ES6) 222 250
Using arbitrary precision math (operating on strings of decimal digits)
This can be golfed a little more(done), but I like the fact that it is not limited to JS standard numbers (17 decimal digits of precision) and that it is fast.
Test running the snippet below in an EcmaScript 6 compliant browser. Time is acceptable up to 9998 - don't try 9999 and be patient with 999.

// As a complete program with I/O via popup
for(n=+prompt(a=[0],q=[t=1]);t;){for(c=1,t=i=0;i<a.length;i++)a[i]=a[i]&c?0:a[i]|c?(c=0,t+=q[i],1):c=0;c&&(a[i]=c,t+=q[i]=q[i-1]*10%n);t%=n}a.reverse().map(a=>(z+=[a],d=z/n|0,z%=n,r||d?r+=d:0),r='',z=0);alert([r,a.join``])

// As a testable function
f=n=>{
  for(a=[0],q=[t=1];t;)
  {
    for(c=1,t=i=0;i<a.length;i++)
      a[i]=a[i]&c?0:a[i]|c?(c=0,t+=q[i],1):c=0
    c&&(a[i]=c,t+=q[i]=q[i-1]*10%n);
    t%=n
  }
  a.reverse().map(a=>(z+=[a],d=z/n|0,z%=n,r||d?r+=d:0),r='',z=0)
  return [r,a.join``]
}

// Test and timing
out = x => O.innerHTML += x + '\n'

setTimeout(_=>{
;[1,2,10, 21, 23, 98, 72, 9, 99, 999]
.forEach((test,i) => {
  var t0 = ~new Date
  var result = f(test)
  out('n='+test+' '+result+' time(ms) ' + (t0-~new Date))
})},100)
<pre id=O>Timing test cases ...
</pre>

More readable
This is the first version, with modulus and long division as separated functions.
// function M - Modulus with arbitrary precision - a is a string of decimal digits
M = (a, b, q = 1, t = 0, j = a.length) => {
  while (j--) + a[j] ? t += q : 0, q = (q * 10) % b;
  return t % b
}

// function D - Long division with arbitrary precision - a is a string of decimal digits
D = (a, b, r = '', z = 0) => [...a].map(a => (z += a, d = z / b | 0, z %= b, r || d ? r += d : 0)) && r

// Testable function
f = n => {
  for (i = 0; ++i < 1e7 && (z = M(v = i.toString(2), n)););
  return z ? ['big'] : [D(v, n), v]
}

I got it to work in Firefox, but it doesn't seem handle bigger numbers, e.g. 999

I'have a new version that can handle 999 in 36 seconds, but there's no hope to reach 9999 with the javascript timeout (each '9' added require 2^9 (~500) times the time to finish)

@aditsu that's the best I can do in JavaScript (but in C# it's quite the same). Eaherly waiting for an explanation of you incredible algorithm

I added an explanation now

Python 3 2, 101 76 Bytes
-25 bytes thanks to @aditsu
almost as efficient as @aditsu's solution
99 -> 0.436 Seconds
72 -> 0.007 Seconds

b,m,n=1,1,input()
while b%n:
 b=int("{0:b}".format(m))
 m+=1
print b/n

Instead of trying to loop through the multiples in increasing order, I'm trying to loop through the products, which I'm generating in 'binary' form.

Not bad :) What about 9999?

Some golfing tips: use python 2 (n=input()), while b%n: (initialize b to 1), no indentation

@aditsu Thanks!  9999 hmmm, looks like it'll take a couple of days, well back to the drawing board -_-

bin(m)[2:] should be shorter than the format string. Double assignment on b=m=1 should save a few as well.

Perl, 45 bytes
do{$a++}while($a*($b||=<>))=~/[2-9]/;print$a;

C++11, many bytes, very fast, wow (1.5 s on 1999999998, 0.2 s on 1…10000)
(Golfed Python version below.)
We start with a concept somewhat similar to aditsu’s solution, where we inductively build up a collection of modular remainders reachable in n steps.  But instead of waiting until we find remainder 0, we check for two found remainders a and b such that a·10^n + b = 0.  This meet-in-the-middle approach halves the depth of the search tree, so it’s much faster on large inputs and uses much less memory.
Some benchmarks:
$ echo 99999999 | \time ./decbin
1111111122222222333333334444444455555555666666667777777788888889
0.18user 0.01system 0:00.20elapsed 99%CPU (0avgtext+0avgdata 69360maxresident)k
0inputs+0outputs (0major+16276minor)pagefaults 0swaps
$ echo 999999999 | \time ./decbin
111111111222222222333333333444444444555555555666666666777777777888888889
1.22user 0.04system 0:01.27elapsed 100%CPU (0avgtext+0avgdata 434776maxresident)k
0inputs+0outputs (0major+37308minor)pagefaults 0swaps
$ echo 2147483647 | \time ./decbin
4661316525084584315813
0.00user 0.00system 0:00.01elapsed 72%CPU (0avgtext+0avgdata 5960maxresident)k
0inputs+0outputs (0major+1084minor)pagefaults 0swaps
$ echo 1999999998 | \time ./decbin
555555556111111111666666667222222222777777778333333333888888889444444445
1.42user 0.08system 0:01.50elapsed 100%CPU (0avgtext+0avgdata 544140maxresident)k
0inputs+0outputs (0major+38379minor)pagefaults 0swaps
$ \time ./decbin 10000.out
0.19user 0.00system 0:00.20elapsed 100%CPU (0avgtext+0avgdata 3324maxresident)k
0inputs+264outputs (0major+160minor)pagefaults 0swaps

Code:
#include <algorithm>
#include <boost/iterator/transform_iterator.hpp>
#include <fstream>
#include <list>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace boost;
using namespace std;

static inline bool cmp_first_partnered(pair<int, pair<int, int>> a,
                                       pair<int, pair<int, int>> b) {
  return a.first < b.first;
}
static inline bool eq_first_partnered(pair<int, pair<int, int>> a,
                                      pair<int, pair<int, int>> b) {
  return a.first == b.first;
}

static pair<int, int> retrace(int modulus, int place, pair<int, int> state,
                              list<vector<int>>::iterator i,
                              list<vector<int>>::iterator j, string &ret) {
  if (i == j)
    return state;
  state = retrace(modulus, (place * 10LL) % modulus, state, next(i), j, ret);
  int remainder = state.first;
  long long k = state.second * 10LL;
  if (!binary_search(i->cbegin(), i->cend(), remainder)) {
    remainder = ((long long)remainder + modulus - place) % modulus;
    k += 1;
  }
  int digit = k / modulus;
  if (digit != 0 || ret.size())
    ret += '0' + digit;
  return make_pair(remainder, k % modulus);
}

static void mult(int modulus, int x, int y,
                 vector<pair<int, pair<int, int>>>::iterator i,
                 vector<pair<int, pair<int, int>>>::iterator j) {
  if (y - x == 1) {
    for (auto k = i; k != j; k++)
      k->first = (k->first * 10LL) % modulus;
    return;
  }

  int z = (x + y) / 2;
  vector<pair<int, pair<int, int>>>::iterator k = lower_bound(
      i, j, make_pair(int(((long long)modulus * z + 9) / 10), make_pair(0, 0)));
  mult(modulus, x, z, i, k);
  mult(modulus, z, y, k, j);
  inplace_merge(i, k, j,
                [](pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
                  return make_pair(a.first, a.second.second) <
                         make_pair(b.first, b.second.second);
                });
}

static string go(int modulus) {
  if (modulus == 1)
    return "1";

  int sequence = 1;
  list<vector<int>> v = {{0}};
  vector<pair<int, pair<int, int>>> partnered;
  int place = 1;
  while (true) {
    v.emplace_back(v.rbegin()->size() * 2);
    vector<int> &previous = *next(v.rbegin()), &current = *v.rbegin();

    auto offset = [modulus, place, sequence](int a) {
      return (a + (long long)place) % modulus;
    };
    auto old_mid =
        lower_bound(previous.cbegin(), previous.cend(), modulus - place),
         new_mid = lower_bound(previous.cbegin(), previous.cend(), place);
    current.resize(
        set_union(new_mid, previous.cend(),
                  make_transform_iterator(previous.cbegin(), offset),
                  make_transform_iterator(old_mid, offset),
                  set_union(previous.cbegin(), new_mid,
                            make_transform_iterator(old_mid, offset),
                            make_transform_iterator(previous.cend(), offset),
                            current.begin())) -
        current.begin());

    int place2 = modulus - (long long)place * place % modulus;
    auto offset_partnered = [modulus, place, place2,
                             sequence](pair<int, pair<int, int>> a) {
      return make_pair((a.first + (long long)place2) % modulus,
                       make_pair((a.second.first + (long long)place) % modulus,
                                 sequence + a.second.second));
    };
    auto old_mid_partnered =
        lower_bound(partnered.cbegin(), partnered.cend(),
                    make_pair(modulus - place2, make_pair(0, 0))),
         new_mid_partnered = lower_bound(partnered.cbegin(), partnered.cend(),
                                         make_pair(place2, make_pair(0, 0)));
    vector<pair<int, pair<int, int>>> next_partnered(partnered.size() * 2 + 1);
    auto i =
        set_union(partnered.cbegin(), new_mid_partnered,
                  make_transform_iterator(old_mid_partnered, offset_partnered),
                  make_transform_iterator(partnered.cend(), offset_partnered),
                  next_partnered.begin(), cmp_first_partnered);
    if (new_mid_partnered == partnered.cend() ||
        new_mid_partnered->first != place2)
      *i++ = make_pair(place2, make_pair(place, sequence));
    next_partnered.resize(
        set_union(new_mid_partnered, partnered.cend(),
                  make_transform_iterator(partnered.cbegin(), offset_partnered),
                  make_transform_iterator(old_mid_partnered, offset_partnered),
                  i, cmp_first_partnered) -
        next_partnered.begin());
    partnered.swap(next_partnered);

    sequence += previous.size();

    place = (place * 10LL) % modulus;

    mult(modulus, 0, 10, partnered.begin(), partnered.end());
    partnered.resize(
        unique(partnered.begin(), partnered.end(), eq_first_partnered) -
        partnered.begin());

    auto with_first = [](int a) { return make_pair(a, make_pair(a, 0)); };

    vector<pair<int, pair<int, int>>> hits;
    set_intersection(partnered.cbegin(), partnered.cend(),
                     make_transform_iterator(current.cbegin(), with_first),
                     make_transform_iterator(current.cend(), with_first),
                     back_inserter(hits), cmp_first_partnered);

    if (hits.size()) {
      pair<int, pair<int, int>> best = *min_element(
          hits.begin(), hits.end(),
          [](pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
            return a.second.second < b.second.second;
          });
      string ret = "";
      pair<int, int> state =
          retrace(modulus, 1, make_pair(best.second.first, 0), v.begin(),
                  prev(v.end()), ret);
      retrace(modulus, 1, make_pair(best.first, state.second), v.begin(),
              prev(v.end()), ret);
      return ret;
    }
  }
}

int main(int argc, const char *argv[]) {
  ios_base::sync_with_stdio(false);
  if (argc >= 2) {
    ofstream ofs(argv[1]);
    for (int modulus = 1; modulus <= 10000; modulus++)
      ofs << go(modulus) << '\n';
  } else {
    int modulus;
    cin >> modulus;
    cout << go(modulus) << '\n';
  }
  return 0;
}

Python, 280 bytes (8.6 seconds on 1999999998 with PyPy)
n=input()
if n<2:print 1;exit()
d={0:0}
l=[]
k=1
b=x=y=0
while 1:
 for a in[0]+l:
  m=(a+k)%n
  if m not in d:l.append(m);d[m]=b
 k=(k*10)%n;b+=1
 for a in l:
  if(-k*a)%n in d:
   while(a-x)%n:x+=10**d[(a-x)%n]
   while(-y-k*a)%n:y+=10**d[(-y-k*a)%n]
   print(10**b*x+y)/n;exit()

I understand that you're after the bounty, but even so this is a [tag:code-golf] question, and the site rules require you to make some effort to golf your code.

@PeterTaylor, very well, I added a golfed version in Python.

1648 bytes

Java, 213 bytes
import java.math.*;class P{public static void main(String[]a){BigInteger b=new java.util.Scanner(System.in).nextBigInteger(),c,d=c=b.ONE;while(!(b.multiply(c)+"").matches("[01]+"))c=c.add(d);System.out.print(c);}}

Uses BigIntegers and as such has (for all reasonable intents and purposes) unbounded input size. Not sure about the complexity though, that depends on the growth rate of our function here.
Thanks to geobits and ypnypn for saving a handful of bytes.

Hi, how would you call this in your main method please? Trying it but not succeeding

You'd have to add the static modifier to the method.

The question says that the solution should be a complete program, not just a function.

You can cut 15 with b.ONE and !(b.multiply(c)+"") (instead of toString()).

@raznagul: Fixed.

You can replace println with print

CJam, 19 17 16 bytes
li:V!{)_V*sAs-}g

Try it online
Brute force solution, trying values sequentially until one meeting the condition is found.
The latest version saves 2 bytes thanks to using As instead of "01" to build a string containing 0 and 1, as suggested by @aditsu. The full proposed solution in the comment saves another byte, but it looks fairly different from mine, so I didn't want to post it under my name.
And 1 more byte saved by @Dennis.
Explanation:
li      Get input and convert to int.
:V      Save it in variable V.
!       Negate the value. Since we saved it in V, we don't need it on the stack anymore.
        But we need 0 on the stack as the start value for y. This conveniently
        accomplishes both with a single operator, since the input is guaranteed to be
        larger than 0.
{       Loop over y.
  )       Increment y.
  _       Copy it.
  V*      Multiply with input in variable V.
  s       Convert to string.
  As      Push the string "10", as the number 10 converted to a string .
  -       Remove 0 and 1 digits. This will result in an empty list if there were only
          0 and 1 digits. The empty list is falsy, and will terminate the loop.
}g      End loop.

16: li0{1$+_sAs-}g\/

Thanks, @aditsu. I didn't really want to copy your full solution under my name. I did take the As to build the string, since it's a very local change, which in hindsight (which is always much easier...) I should have thought of.

@RetoKoradi 16 bytes, less modifications: li:V!{)_V*sAs-}g Also, 0{)_easi*sAs-}g (15 bytes) works with the Java interpreter and command-line arguments.

Pyth, 10 bytes
f<eS`*TQ`2

Run the code.
A port of my Python answer, taking from Maltysen the use of f to find the first positive number that meets a condition.

PHP, 50 bytes
while(preg_match('/[^01]/',$argv[1]*++$y));echo$y;

Some test cases
1 > 1
2 > 5
12 > 925
21 > 481

Was gonna make something like this, this is even a tad shorter than I had in mind

Mathematica 115 bytes
p=Drop[Union[FromDigits/@Flatten[Table[Tuples[{0,1},{k}],{k,2,12}],1]],2];
i=Input[];FirstCase[p,x_/;Divisible[x,i]]

R, 45 bytes
x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y

Usage:
> x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y
1: 2
2:
Read 1 item
[1] 5
> x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y
1: 21
2:
Read 1 item
[1] 481
> x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y
1: 42
2:
Read 1 item
[1] 2405

Java 156 bytes
public class P{public static void main(String[]a){long x=Long.valueOf(a[0]),y;for(y=2;!(""+x*y).replaceAll("1|0","").isEmpty();y++);System.out.println(y);}}

Massive thanks to aditsu :)

You don't need a space after [], y can be long too, you forgot the x*y+"" trick in the 2nd program, use isEmpty instead of checking the length, use ; instead of {}

Anyway, welcome to code golf :)

I must say, I am impressed, but making y long wouldn't make the code shorter

Yes it would: long x=…,y;

y must start from 1, you can initialize it in the declaration, your class doesn't need to be public, and you can move y++ to the x*y part (x*y++)

C, 107 101 bytes (105 99 bytes for 32-bits)
There is a distinct lack of answers in C on code golf. Indeed, C is not the best choice for writing the smallest possible program, but it's not that bad:
main(d,b){char s[9];gets(s);for(b=atoi(s);sprintf(s,"%d",b*d),strspn(s,"01")[s];d++);printf("%d",d);}

You can do without the #includes, but then all the function definitions will be implicit. The main drawback is that this causes the assumption that all functions return ints. This is a problem on 64-bit machines for functions that actually return a pointer. If you are on a 32-bit machine, 2 bytes can be shaved off the above solution:
main(d,b){char s[9];for(b=atoi(gets(s));sprintf(s,"%d",b*d),strspn(s,"01")[s];d++);printf("%d",d);}

Somewhat more readable version:
int main()
{
  char s[9];
  gets(s);
  int d = 1;
  int b = atoi(s);
  for (; sprintf(s, "%d", b * d), strspn(s, "01")[s]; d++);
  printf("%d", d);
}

C# time near 5 seconds (1 to 10000)
As requested, here is a golfed C# program answering the original challenge.
Input as command line argument, output to console.
using System;using System.Collections.Generic;using System.Numerics;using System.Linq;
class P{static void Main(string[] a){int m,n=int.Parse(a[0]);var d=new Dictionary<int,long>();long b;int h;
for(d[n]=0,b=h=1;;b*=2,h=(h*10)%n)foreach(int k in d.Keys.Reverse())if(!d.ContainsKey(m=(h+k)%n)){
var w=d[k]|b;if(m==0){Console.Write(BigInteger.Parse(Convert.ToString(w,2))/n);return;}d.Add(m,w);}}}

Then, as for the bounty: the bounty should go to aditsu, as I think his algorithm cannot be beaten in terms of perfomance. But anatolyg self-answer is amazing too.
Here is my fast implementation in C#. I suppose that in C++ it could be faster (maybe 2x). Compiled and tested with Visual Studio 2010, .NET framework 4, 64 bits, redirecting output to nul. Time : 00:00:05.2604315
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Diagnostics;

class Program
{
   static BigInteger Find(int n)
   {
      var d = new Dictionary<int, long>();
      long kb;
      int km;
      d[n] = 0;
      for (kb = km = 1; ; kb *= 2, km = (km * 10) % n)
      {
         foreach (int key in d.Keys.Reverse())
         {
            int m = (km + key) % n;
            if (!d.ContainsKey(m))
            {
               long w = d[key] | kb;
               if (m == 0)
               {
                  return BigInteger.Parse(Convert.ToString(w, 2));
               }
               d.Add(m, w);
            }
         }
      }
   }

   static void Exec(int n, out string sq, out string sa)
   {
      var v = Find(n);
      sq = (v/n).ToString();
      sa = v.ToString();
   }

   static void Main(string[] args)
   {
      // string n = Console.ReadLine();
      int limit = int.Parse(args[0]);
      string q ="", a = "";
      Stopwatch x = new Stopwatch();
      x.Start();
      for (int n = 1; n <= limit; n++)
      {
         Exec(n, out q, out a);
         Console.WriteLine("{0} {1} {2}", n, q, a);
      }
      x.Stop();
      Console.Error.WriteLine("{0}", x.Elapsed);
   }
}

Times 4.1s. I misspoke in the bounty. With the latest version of PyPy, aditsu's faster version times approximately 8s, so this is twice as fast.

I understand that you're after the bounty, but even so this is a [tag:code-golf] question, and the site rules require you to make some effort to golf your code.

I'm not after the bounty, it's just an example of implementation. But you're right, I'll add a golfed version.

@PeterTaylor could it go now?

By the way, why Keys.Reverse? Is the order important? If it's just to avoid concurrency issues, ToList is shorter.

@PeterTaylor yes ToList is ok (but I'm not sure why, Reverse seems faster)

Pyth - 12 11 bytes
Uses filter with numeric arg to get first natural number that fulfills predicate, default is 1 which is what we want. Setwise diff to check if only zeros and ones.
f!-j*QT10U2

Test Suite.

Convert to string and remove "01. Saves one char.

Java, 198 193 181 bytes
Thanks to @aditsu for shaving off 5 bytes AND increasing the range of testable numbers!
Note that some values loop negatively due to how Java parses integers. This could be circumvented by BigInteger, but the bonus was simply less valuable.
I know that I'm not going to win, but I hope this inspires other, shorter, answers.
class A{public static void main(String[] a){for(long i=1;;i++){try{long b=Long.parseLong(a[0]);if(b*i<0)break;Long.parseLong(b*i+"",2);System.out.println(i);}catch(Exception e){}}}}
Ungofled:
class A {
   public static void main(String[] a){
      for(long i=1;;i++){ // infinite loop starting at 1
         try{ // if an error is thrown by attempting to parse as binary, restart while adding 1 to i
            long b=Long.parseLong(a[0]); // For later - it was shorter to declare than use twice
            if(b*i<0)break; // Break out of the program if we have looped.
            Long.parseLong(b*i+"",2); // Multiply out and see if it's passable as a binary number, otherwise, throw error and go back to the top of the loop
            System.out.println(b); // print it out
         } catch (Exception e) {} // do nothing on catch
      }
   }
}

It's funny that Long is shorter than Integer :)

The most literal irony there is.

C with GMP (621 bytes, fast)
I've tried to be fast and short, but favoured fast. This implementation uses a slightly improved version of the number-theoretic speedup I mentioned in a comment on aditsu's answer.
Save as pseudobinary.c and compile with gcc pseudobinary.c -lgmp -o pseudobinary. Note that this allocates so much memory for large inputs that you will need to compile it for a 64-bit platform.
#include <gmp.h>
int main(int y,char*z[]){int i,n,b,c,e,f,m,*j,*k,*l,*r,*h;char *d,*s;mpz_t
B,I,Q;i=atoi(z[1]);n=i;for(b=0;n%10<1;++b)n/=10;for(;n%2<1;++b)n/=2;for(;n%5<1;++b)n/=5;if(n<2)--b;d=calloc(n,1);j=calloc(n,sizeof(int));r=calloc(99,sizeof(int));c=2;d[1]=1;*j=r[1]=e=1;l=j+1;for(s=0;!s;++c){r[c]=e=e*10%n;k=l;for(h=j;h<k;h++){f=*h;m=(e+f)%n;if(d[m]<1){*l++=m;if(m<1){s=malloc(99);memset(s,48,99);for(f=c;f;f=d[m=(m+n-r[f])%n])s[c-f]++;s[c]=0;h=k;}d[m]=c;}}}f=strlen(s);s[f]=48;s[f+b]=0;mpz_init_set_str(B,s,10);mpz_init_set_si(I,i);mpz_init(Q);mpz_divexact(Q,B,I);d=mpz_get_str(0,10,Q);printf("%s\n",d);return 0;}

Loop version for timing (751 bytes)
#include <gmp.h>
char **v;int main(){int i,n,b,c,e,f,m,*j,*k,*l,*r,*h;char *d,*s;mpz_t
B,I,Q;v=calloc(10001,sizeof(char*));v[1]=s=malloc(99);memset(s,48,99);*s=49;s[1]=0;for(i=0;++i<10001;){n=i;for(b=0;n%10<1;++b)n/=10;for(;n%2<1;++b)n/=2;for(;n%5<1;++b)n/=5;d=calloc(n,1);j=calloc(n,sizeof(int));r=calloc(99,sizeof(int));c=2;d[1]=1;*j=r[1]=e=1;l=j+1;for(;!v[n];++c){r[c]=e=e*10%n;k=l;for(h=j;h<k;h++){f=*h;m=(e+f)%n;if(d[m]<1){*l++=m;if(m<1){v[n]=s=malloc(99);memset(s,48,99);for(f=c;f;f=d[m=(m+n-r[f])%n])s[c-f]++;s[c]=0;h=k;}d[m]=c;}}}free(d);free(j);free(r);s=v[n];f=strlen(s);s[f]=48;s[f+b]=0;mpz_init_set_str(B,s,10);mpz_init_set_si(I,i);mpz_init(Q);mpz_divexact(Q,B,I);d=mpz_get_str(0,10,Q);printf("%s\n",d);free(d);s[f+b]=48;s[f]=0;}return 0;}

Ungolfed loop version
#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char **cache;

int main() {
    int i,n,shift,_kb,km,key,m,*ks,*ksi,*nksi,*res,*ii;
    char *d,*s;
    mpz_t B,I,Q;

    cache = calloc(10001,sizeof(char*));
    if (!cache) { printf("Failed to malloc cache\n"); return 1; }
    cache[1]=s = malloc(99);
    memset(s,48,99);
    *s=49;
    s[1]=0;
    for (i=0;++i<10001;) {
        n=i;
        for(shift=0;n%10<1;++shift)n/=10;
        for(;n%2<1;++shift)n/=2;
        for(;n%5<1;++shift)n/=5;

        d = calloc(n,1);
        if (!d) { printf("Failed to malloc d\n"); return 1; }

        ks = calloc(n,sizeof(int));
        if (!ks) { printf("Failed to malloc ks\n"); return 1; }

        res = calloc(99,sizeof(int));
        if (!res) { printf("Failed to malloc res\n"); return 1; }

        _kb = 2;
        d[1] = 1;
        *ks = res[1] = km = 1;
        nksi = ks + 1;

        for(;!cache[n];++_kb) {
            res[_kb] = km = km*10%n;
            ksi = nksi;
            for (ii = ks; ii < ksi; ii++) {
                key = *ii;
                m = (km + key) % n;
                if (d[m] < 1) {
                    *nksi++ = m;
                    if (m < 1) {
                        cache[n] = s = malloc(99);
                        if (!s) { printf("Failed to malloc s\n"); return 1; }
                        memset(s,48,99);
                        for(key=_kb;key;key = d[m = (m + n - res[key]) % n])s[_kb-key]++;
                        s[_kb]=0;
                        ii = ksi; // break
                    }
                    d[m] = _kb;
                }
            }
        }

        free(d);
        free(ks);
        free(res);

        // Add shift * '0'
        s=cache[n];
        key=strlen(s);
        s[key]=48;
        s[key+shift]=0;

        // convert to big integer, divide, print
        mpz_init_set_str(B,s,10);
        mpz_init_set_si(I,i);
        mpz_init(Q);
        mpz_divexact(Q,B,I);
        d = mpz_get_str(0,10,Q);
        if (!s) { printf("Failed to malloc quotient\n"); return 1; }
        printf("%s\n", d);
        free(d);

        // Remove shift * '0'
        s[key+shift]=48;
        s[key]=0;
    }
    return 0;
}

C + GMP, 669
This is really fast for smallish numbers; it starts to choke when the result has more than 64 digits.
#include<gmp.h>
#define B(x)(int)((x*(long)k)%n);
int*M,*H,P[99],n,x,p,q=2,e=1,k=10,y,f,z;char*E,C[99];int b(int k,int t){int
j=E[k],a=1<<(j-2);if(j<2){C[t]=49;return 1;}x=(int)((k+n-P[j]*(long)H[k]%n)%n);if(x)b(x,t);return a+b(H[k],t-a);}int
main(){scanf("%d",&n);E=calloc(n+1,1);M=calloc(n+1,4);H=malloc(n*4);M[1]=E[1%n]=P[1]=1;while(!E[0]){P[++e]=k;p=q;for(x=0;++x<p;){y=B(M[x])if(E[n-y]){E[0]=e;H[0]=M[x];break;}}if(!E[x=0])while(++x<p){y=B(M[x])for(z=0;z<p;++z){f=y+M[z];if(f>=n)f-=n;if(!E[f]){E[f]=e;H[f]=M[x];M[q++]=f;}}}k=B(k)}memset(C,48,98);C[99]=0;x=b(0,97);mpz_t
m,r;mpz_init(r);mpz_init_set_str(m,C+98-x,10);mpz_fdiv_q_ui(r,m,n);puts(mpz_get_str(C,10,r));}

Version that loops to 10000 (671 bytes):
#include<gmp.h>
#define B(x)(int)((x*(long)k)%n);
#define N 10001
int M[N],H[N],P[99],n=0,x,p,q,e,k,y,f,z;char E[N],C[99];int b(int k,int t){int
j=E[k],a=1<<(j-2);if(j<2){C[t]=49;return 1;}x=(int)((k+n-P[j]*(long)H[k]%n)%n);if(x)b(x,t);return a+b(H[k],t-a);}int
main(){while(++n<N){memset(E,M[0]=0,n);M[1]=E[1%n]=P[1]=e=1;q=2;k=10;while(!E[0]){P[++e]=k;p=q;for(x=0;++x<p;){y=B(M[x])if(E[n-y]){E[0]=e;H[0]=M[x];break;}}if(!E[x=0])while(++x<p){y=B(M[x])for(z=0;z<p;++z){f=y+M[z];if(f>=n)f-=n;if(!E[f]){E[f]=e;H[f]=M[x];M[q++]=f;}}}k=B(k)}memset(C,48,98);C[99]=0;x=b(0,97);mpz_t
m,r;mpz_init(r);mpz_init_set_str(m,C+98-x,10);mpz_fdiv_q_ui(r,m,n);puts(mpz_get_str(C,10,r));}}

Here are some commands for testing my code as well as my competitors', and the results on my laptop:
ls -l *.c*
-rw-r--r-- 1 aditsu aditsu  669 Oct 27 15:01 mult-aditsu-single.c
-rw-r--r-- 1 aditsu aditsu  671 Oct 27 15:01 mult-aditsu.c
-rw-r--r-- 1 aditsu aditsu 3546 Oct 27 15:01 mult-anatoly.c
-rw-r--r-- 1 aditsu aditsu 6175 Oct 27 15:01 mult-anders.cpp
-rw-r--r-- 1 aditsu aditsu  621 Oct 27 15:01 mult-peter-single.c
-rw-r--r-- 1 aditsu aditsu  751 Oct 27 15:01 mult-peter.c

gcc -w -march=native -O3 mult-aditsu-single.c -lgmp -o mult-aditsu-single
gcc -w -march=native -O3 mult-aditsu.c -lgmp -o mult-aditsu
gcc -w -march=native -O3 mult-peter-single.c -lgmp -o mult-peter-single
gcc -w -march=native -O3 mult-peter.c -lgmp -o mult-peter
gcc -w -march=native -O3 --std=c99 mult-anatoly.c -o mult-anatoly
g++ --std=c++11 -march=native -O3 mult-anders.cpp -o mult-anders

for i in {1..5}; do time ./mult-anders mult-anders.txt; done
./mult-anders mult-anders.txt  0.34s user 0.00s system 99% cpu 0.344 total
./mult-anders mult-anders.txt  0.36s user 0.00s system 99% cpu 0.358 total
./mult-anders mult-anders.txt  0.34s user 0.00s system 99% cpu 0.346 total
./mult-anders mult-anders.txt  0.35s user 0.00s system 99% cpu 0.347 total
./mult-anders mult-anders.txt  0.34s user 0.00s system 99% cpu 0.344 total

for i in {1..5}; do ./mult-anatoly mult-anatoly.txt; done
Time: 0.254416
Time: 0.253555
Time: 0.245734
Time: 0.243129
Time: 0.243345

for i in {1..5}; do time ./mult-peter > mult-peter.txt; done
./mult-peter > mult-peter.txt  0.14s user 0.00s system 99% cpu 0.137 total
./mult-peter > mult-peter.txt  0.15s user 0.00s system 97% cpu 0.153 total
./mult-peter > mult-peter.txt  0.15s user 0.00s system 99% cpu 0.149 total
./mult-peter > mult-peter.txt  0.15s user 0.00s system 99% cpu 0.150 total
./mult-peter > mult-peter.txt  0.14s user 0.00s system 99% cpu 0.138 total

for i in {1..5}; do time ./mult-aditsu > mult-aditsu.txt; done
./mult-aditsu > mult-aditsu.txt  0.06s user 0.00s system 95% cpu 0.058 total
./mult-aditsu > mult-aditsu.txt  0.05s user 0.00s system 97% cpu 0.055 total
./mult-aditsu > mult-aditsu.txt  0.06s user 0.00s system 99% cpu 0.056 total
./mult-aditsu > mult-aditsu.txt  0.05s user 0.00s system 99% cpu 0.054 total
./mult-aditsu > mult-aditsu.txt  0.05s user 0.00s system 98% cpu 0.055 total

md5sum *.txt
6eef8511d3bc5769b5d9218be2e00028  mult-aditsu.txt
6eef8511d3bc5769b5d9218be2e00028  mult-anatoly.txt
6eef8511d3bc5769b5d9218be2e00028  mult-anders.txt
6eef8511d3bc5769b5d9218be2e00028  mult-peter.txt

An answer well-deserving of a bounty. I take particular interest in this problem (and your initial solution), because it is a special case of the subset sum problem, which is known to be NP-complete (given a list of the residues of 10ⁱ mod n, find the earliest subset which sums to n).

@primo Thank you :) My approach here is different - I double the number of digits at each step rather than just incrementing it, and I also check first (very quickly) if any of the new numbers would be a solution, before actually calculating them. And I'm sure there's still room for golfing.

Interesting. When I tried doubling the number of digits at each step it ended up being slower. Maybe the pre-check for solutions makes a big difference.

@PeterTaylor that's possible.. it seems that you're also calling calloc in a loop, which might slow it down. Anyway, I'd like to add an ungolfed version of my code when I find some time, and I also have an idea how to make it faster for bigger/nastier numbers.

T-SQL, 164 156 155 154 159 bytes
(-1 byte. Thanks Jonathan!)
(-1 more because why do I have trailing spaces on lines? SMH)
(+5 realized my golfing broke things)
create function b(@ int)
returns int
as begin
declare @b varchar(max)='',@i int=@
while @>0SELECT @b=cast(@%2 as varchar)+@b,@/=2
return cast(@b as int)/@i
end

I don't know why I keep coming back to these questions where I'm supposed to convert to Binary... T-SQL doesn't know how to do that right.
In any case, here's a SQLFiddle.
Un-golfed:
create function binarySquare(@id int)
returns int
as BEGIN

Most of this stuff is required to write a function in T-SQL, as far as I'm aware.
    declare @bin nvarchar(max) = ''

Create a blank string that we're going to store as our binary number.
    declare @id2 int = @id

Save the input value for use at the end. It seems like there should be a way to use the original input even if we change the value, but I can't find one.
    while @id>0
      BEGIN
        SET @bin = cast(@id%2 as varchar(1)) + @bin

So we take our original input, MOD it with 2 to find the remainder, and that's going to be our next smallest digit. For example, 5%2 = 1
        SET @id = @id/2

Then we take our number, and divide it in half. Because it's an int type, it rounds it down to the nearest whole number, so 5/2 = 2.
          END
We then loop through this until the value is 0. So we end up with
    5%2 = 1    5/2 = 2
    2%2 = 0    2/2 = 1
    1%2 = 1    1/2 = 0
which gives us our binary string value of 101.
    declare @binNum int = (SELECT cast(@bin as int))

We take our binary string and convert it back to an int again.
    return @binNum/@id2

We return our binary string int divided by our original value, per the origin of the question.
END

Is the space in @>0 SELECT not omittable?

Nice catch! I can never remember what spaces are omit-able...

Most of the time you can omit spaces in between literals and variables / keywords, as they cannot begin with a digit.

Julia, 38 bytes (brute force approach)
~n=(i=0;while"$((i+=1)n)"⊈"01"end;i)

Attempt This Online!

-7 bytes (!!) thanks to MarcMush: rewrite with ⊈ instead of maximum
-1 byte thanks to MarcMush: increment i inside the loop evaluation

38 bytes with ⊈: ~n=(i=0;while"$((i+=1)n)"⊈"01"end;i)

Scala, 114 Bytes
val i=scala.io.StdIn.readInt;Stream.from(1).foreach{x=>if((i*x+"").map{_.asDigit}.max<2){print(x);System.exit(0)}}

Readable version
val i=scala.io.StdIn.readInt
Stream.from(1).foreach{x =>
    if((i*x+"").map{_.asDigit}.max<2) {
        print(x)
        System.exit(0)
    }
}

gawk4 brute force, 28+2 = 30 bytes
{while(++n*$0~/[2-9]/);}$0=n

Needs to be called with the -M option for using big numbers. Of course this is ridiculously slow, using big numbers slows it down even more, but theoretically the input is not limited, and RAM usage is negligible.
Usage example ( if you got time to waste ;))
echo 27 | awk -M '{while(++n*$0~/[2-9]/);}$0=n'

gawk4 optimized, 69+2 = 71 bytes
{for(;!a[0];NR*=10)for(i in a)a[j=(s=a[i]+NR)%$0]?0:a[j]=s}$0=a[0]/$0

Well, this ended up being a clone of aditsu's answer. After looking at this question I was still figuring out how to code the subset-sum part, when I couldn't resist looking at the other answers here.
In awk array elements have the (strange ?) behaviour that if you compare a non-existing element to something it is somehow initialized as empty before being compared (I'll admit that I'm not quite sure about what is happening there). So after checking !a[0] the for(i in a) loop starts even without initializing a[$0] to 0 as aditsu did.
Of course the -M option has to be used for this too.
Though it is rather fast it is still remarkably slower than Python. For 79992 this takes around 14 seconds on my 2GHz Core2Duo. And I wouldn't say it works for inputs up to 2^31, because in the worst case it has to build an array of big numbers (gawk4 uses GMP for this), which has the size of the input number. As a 'bonus' large arrays are very very slow in awk...

Dyalog APL, 25
This defines a proper program "P" (not just an unnamed function):
P←2∘{0::⍵∇⍨1+⍺⋄⍺⊣~⍎¨⍕⍺×⍵}

2∘ begin with 2 as left argument
0:: if there is any error...
⍵∇⍨1+⍺ call itself with an incremented left argument
⍺×⍵ multiply left and right arguments
⍕ make into string
⍎¨ make each character into a number
~ attempt logical NOT (if it fails, go to error-handling above, else...)
⍺⊣ return the current left argument.
      P 2
50
      P 21
481
      P¨⍳8    ⍝ 1 through 8
10 5 37 25 2 185 143 125

Ruby, 46 bytes
I should really eliminate the while loop with an alternative loop.
n,k=gets,0;$_="#{n.to_i*k+=1}"while/[^01]/;p k

Edit: Thanks @manatwork for shaving off 1 byte!
Edit2: Thanks @histocraft for the insane 9 bytes!
Edit: Thanks @manatwork again for shaving off 7 bytes!

z!=z[/[01]+/] is shorter. z[/[^01]/] is even more shorter.

@manatwork Thanks! 1 byte less!

Single-line while loops tend to be the shortest: z="#{n.to_i*k+=1}"while z[/[^01]/]

@histocrat That's 9 bytes! And I didn't even know that ruby is capable of this. Thanks!

Interesting that you not changed the test to negated character set neither after was suggested 2nd time. Any reason?

@manatwork I've thought about that and tried it but the loop never ended for me (which is strange)

oh, must be because of the trailing newline returned by gets the way you're invoking it.

With some Perlish flavor: n=gets;k=0;$_="#{n.to_i*k+=1}"while/[^01]/;p k.

Jelly, 8 bytes
×QḌ=⁵ð1#

Try it online!
Tied Pyth!
How it works
×QḌ=⁵ð1# - Main link. Takes n on the left
     ð   - Combine the previous links into a dyad f(i, n):
×        -   i×n
 Q       -   Unique digits
  Ḍ      -   Convert into an integer
   =⁵    -   Does this equal 10?
           f(i, n) returns true for a given i if i×n only consists of 1 and 0
      1# - Starting from n, find the first integer i = n, n+1, ... such that f(i, n) is true

Vyxal, 13 bytes
∞›*'S₀S↔=;h$/

Try it Online!
∞›*           # All multpiles of n
   '     ;    # Filtered by
    S₀S↔      # When you remove all the digits except 0 and 1
        =     # Does it equal itself?
          h   # Get the first item for which this happens
           $/ # Divide by n

Thunno 2, 4 bytes
Ƙ×Gḅ

Try it online!
Explanation
Ƙ×Gḅ  # Implicit input
Ƙ     # First integer where:
 ×    #  Multiply by the input
  G   #  Maximum digit
   ḅ  #  Equals one?
      # Implicit output

Vyxal, 82 bitsv2, 10.25 bytes
¨*'₀τGċ¬;h?/

Try it Online!

Vyxal, 44 bitsv2, 5.5 bytes
?*↑ṅ)ṅ

Try it Online!

PowerShell Core, 36 bytes
for(;++$i*"$args"-replace"[01]"){}$i

Try it online!

SAS, 81 bytes
This is give or take the same approach as some of the 'fast' python approaches above: iterate through the possible binary numbers, pretend they're decimal, test them.
data a;b=72;do until(a=int(a));y+1;a=input(put(y,binary32.),32.)/b;end;put a;run;

Unfortunately I can't skip the input/put, because the default width for implicit conversions is only 12 (meaning it quickly becomes "1e8" and similar which fails).
Ungolfed:
data a;
  b=72;
  do until(a=int(a));
    y+1;
    a=input(put(y,binary32.),32.)/b;
  end;
  put a;
run;

This isn't entirely safe; for larger numbers (which have no solution in a double precision floating point environment) this could turn into an infinite loop.

Ruby 46 bytes
No better in # of bytes than the previous Ruby solution by the Peter Lenkefi, but slightly different approach:
gets;p 1.step.find{|i|"#{$_.to_i*i}"!~/[^01]/}

C#, 156+31=187 bytes
The code requires the following usings:
using System;using System.Linq;

Here the code:
class P{static void Main(string[]a){var b=ulong.Parse(Console.ReadLine());var d=1U;for(;(b*d).ToString().Any(x=>x!='0'&&x!='1');d++);Console.WriteLine(d);}}

Ungolfed:
using System;
using System.Linq;

class P
{
    static void Main(string[] a)
    {
        var b = ulong.Parse(Console.ReadLine());
        var d = 1U;
        for (; (b*d).ToString().Any(x => x != '0' && x != '1'); d++);
        Console.WriteLine(d);
    }
}

Burlesque, 24 bytes
Found a shorter version:
1R@?*b0{{"10"j~[}al}fi?i

Older Versions:
1R@?*b0{"\`[01]*\\'"~=}fi?i

It's terribly slow though if the number can't be found fast.
1R@?*b0{"23456789"INnu}fi?i

This version might be faster because it doesn't use regexes. Still terribly slow though.
There's no limit except the time it takes to find the answer which can be quite long.

Japt, 13 12 10 bytes
È*U skA}f1

Try it - Be careful with multiples of 9 ;)

Husk, 9 bytes
ḟö=1▲d*⁰N

Try it online!
ḟö=1▲d*⁰N
ḟö              # first truthy element of:
      *⁰N       # multiply all natural numbers by input
    ▲d          # max of decimal digits
  =1            # equals 1

Ruby, 36 bytes
->n{(1..).find{(_1*n).digits.max<2}}

Attempt This Online!

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Interlocking Brackets
Write a program or function that takes in an eight byte string containing one of each of the characters ()[]{}<> arranged in any way such that the four respective bracket types match. For example, ]<([){}> is invalid input because the square brackets don't match (though all the others do).
Print or return an integer from 0 to 6 that denotes how many of the six possible pairings of the four bracket types are interlocked. Bracket type pairs are considered interlocked if exactly one bracket of one type occurs between the brackets of the other type. So ([)] and [(]) are interlocked but ()[], [](), ([]), and [()] are not.
The shortest code in bytes wins.
Input/Output Examples
()[]{}<> : 0
([{<>}]) : 0
<>{[]}() : 0
{<>([])} : 0
<(>)[{}] : 1
<[({)}]> : 1
[{<}]>() : 2
{<>([}]) : 2
<{(>})[] : 3
[(]<){>} : 3
<([>{)}] : 4
(<{[>})] : 4
(<[{)>}] : 5
<{[(>})] : 5
[{<(]}>) : 6
(<{[)>}] : 6

CJam, 18
l7~f&_f{\/~;&}s,2/

Thanks isaacg for some golfing ideas :)
Try it online or try all examples
Explanation:
l         read a line of input
7~f&      clear the lowest 3 bits of each character
           the goal is to convert brackets of the same type to the same char
_         duplicate the resulting string, let's call it S
f{…}      for each character in S, and S (the char and S are pushed every time)
  \       swap the character with S
  /       split S around that character, resulting in 3 pieces:
           before, between, after
  ~       dump the pieces on the stack
  ;       pop the last piece
  &       intersect the first 2 pieces
          after the loop, we have an array of strings
          containing the chars interlocking to the left with each char of S
s         join all the string into one string
,         get the string length
2/        divide by 2, because S has duplicated characters

Oh, so you're the guy who created CJam?? You owe me for all the answers I lost that got beaten by CJam answers! ;)

@kirbyfan64sos well, you'd better start learning it too if you want to win :)

7~f&? I like this answer already, and I haven't even read the rest of it.

Python 2, 163 bytes
def f(b,e='([{<)]}>',q=range(4)):
 b=[b[b.index(e[j])+1:b.index(e[j+4])]for j in q]
 print sum(sum(abs(b[k].count(e[j])-b[k].count(e[j+4]))for j in q)for k in q)/2

This looks at the stuff between each pair of matching brackets and counts the number of individual left or right brackets present. The sum of these divided by two is the output.
I'm sure it could be golfed a lot more by better golfers than me.

Well, it happened. Calvin posted an answer. The end times are upon us.

GNU sed -r, 147
Output is in unary as per this meta-answer.
y/([{</)]}>/
s/.*/\t& & & & /
:b
y/)]}>/]}>)/
s/\S*>(\S*)>\S* /\1\t/
t
s/\S* //
:
s/(\t\S*)(\S)(\S*)\2(\S*\t)/\1\3\4/
t
s/\S *$/&/
tb
s/\s//g
s/../1/g

Note: Replace \t with actual tab characters to get the correct score.  However, the program will work either way with GNU sed.
Try it online.

Retina, 128 108 64 62 55 bytes
(T`)]>}`([<{
(\D)(.*)\1(.*)
\n$2\n$3
(?=(\D).*\n.*\1)
1
\n
<empty>

Where <empty> represents an empty trailing line. For counting purposes, put each line in a separate file, and replace the \n with actual linefeed characters. For convenience, you can use this equivalent code with the -s flag from a single file:
(T`)]>}`([<{
(\D)(.*)\1(.*)
#$2#$3
(?=(\D)[^#]*#[^#]*\1)
1
#
<empty>

Output is unary.
Explanation
The first ( tells Retina to execute the entire code in a loop until an iteration stops changing the string. In this case, it will always iterate four times, once for each bracket type.
T`)]>}`([<{

This simply turns each closing bracket into the corresponding opening bracket, so that we can match corresponding brackets with a simple backreference later on. (This stage becomes a no-op after the first iteration. It's only included in the loop, because the T already required a backtick, so adding ( cost only one instead of two bytes.)
(\D)(.*)\1(.*)
\n$2\n$3

This replaces the left-most pair of brackets with newlines. We use \D to distinguish brackets from the 1s we add later in the loop for counting. The (.*) at the end ensures that only one pair is replaced (because matches cannot overlap).
(?=(\D).*\n.*\1)
1

The entire regex is in a lookahead, so this matches a position. More specifically it matches one position for each pair of brackets which has been separated by the other brackets we just turned into newlines. A 1 is inserted into each of these positions. We can just leave the 1s there, because they don't affect any of the other regexes (because the \Ds ensure that we don't match them accidentally).
\n
<empty>

Finally, we remove the newlines (i.e. the placeholders for the current type of brackets) - this means that we've reduced the remaining problem to a string of length 6 containing only 3 types of brackets, but otherwise it works exactly the same.
At the end, only the 1s we inserted will be left, and their amount corresponds exactly to the number of interlocking brackets.

Perl, 77 bytes
76 code + 1 switch
perl -pe 'y/)]}>/([{</;for$x(/./g){$h{$x="\\$x"}++&&s!$x(.*)$x!$z+=length$1,$1!e}$_=$z'

Takes input from STDIN and the program must be started fresh for every input.
Explanation

Replace all closing brackets with their open counterparts (y/.../.../).
Then, for every character in the input string (for$x...), increment a counter for the character ($h{$x}++).
If this is the second time we're seeing the character, get the distance between the two occurances (length $1) and remove both occurances of this character from the string. For example, if the string was ([{([{<<, there are two characters [ and { between the two (s. After the (s are processed, the string becomes [{[{<< and we add 2 to the total number ($z) of interlocking brackets.
The result is taken from $z ($_=$z)

Python 3, 107
t=0
s=""
for x in input():s+=chr(ord(x)&~7)
for x in s:a=s.split(x);t+=len(set(a[0])&set(a[1]))
print(t//2)

Loosely based on my CJam solution.

Pyth, 20 bytes
JmC/CdTzlsm@FPcsJd{J

Test suite
JmC/CdTz: First, this converts each symbol pair to a single character by map each input character to its character code (Cd) divided by 10 (/  T), which is the same for each pair but different between all pairs. The resultant number is converted back into a character for purposes to be revealed later (C). The resultant list of characters is saved to J.
lsm@FPcsJd{J: Now, we map over the unique characters in J ({J). We start by chopping the string formed by concatenating J using the current character as the delimeter (csJd). A pair of brackets overlaps the current pair if it appears in the second group and either the first or third group. To avoid double counting, we'll just count the first and second group case. So, we remove the third group (P) and take the intersection of the remaining groups (@F). Finally, we concatenate the overlap characters (s) and print the length of the resut (l).

JavaScript (ES7), 121 117 bytes
x=>(a=b=0,[for(c of x)for(d of'1234')(e=c.charCodeAt()/26|0)==d?a^=1<<d:b^=(a>>d&1)<<d*4+e],f=y=>y&&y%2+f(y>>1))(b)/2

Wow. That was fun. I sketched out an answer idea when this challenge first came out, but it was over 150 bytes long and I didn't want to put in the effort to golf it. I ran across this idea in my notebook yesterday and decided I wouldn't stop thinking about it until I had fully golfed it. I ended up writing out two entirely new algorithms, the first of which ended up several bytes shorter after golfing off around 25 bytes with tons of bit-hacking.
How it works
First we set variables a and b to 0. a is a 4-bit binary array of which bracket pairs we are currently inside, and b is a 16-bit binary array of which bracket pairs are linked together.
Next, we loop through each character c in x, and each char d in '0123'. First we determine what type of bracket c is with e=c.charCodeAt()/26-1|0. The decimal char codes of each bracket type are as follows:
() => 40,41
<> => 60,62
[] => 91,93
{} => 123,125

By dividing by 26, subtracting 1, and flooring, we map these to 0, 1, 2, and 3, respectively.
Next we check if this number is equal to the current value of d. If it is, we are either entering or exiting the dth bracket type, so we flip the dth bit in a with a^=1<<d. If it's not, but we are inside the dth bracket type, we need to flip the eth bit in the dth 4-bit section of b. This is done like so:
b^=(a>>d&1)<<d*4+e

(a>>d&1) Returns the dth bit in a. If we are inside the dth bracket type, this returns 1; otherwise, it returns 0. Next, we shift this left by d*4+e bits, and XOR b by the result. If we are inside the dth bracket type, this XORs the d*4+eth bit of b; otherwise, it does nothing.
At the end of all the looping, b will contain a number of 1-bits equal to twice the desired return value. But we still need to figure out how many bits this is. That's where the sub-function f comes in:
f=y=>y&&y%2+f(y>>1)

If y is 0, this simply returns 0. Otherwise, it takes the last bit of y with y%2, then adds the result of running all but the last bit y through the function again. For example:
f(y)         => y && y%2 + f(y>>1)
f(0b1001101) =>       1  + f(0b100110) = 4
f(0b100110)  =>       0  + f(0b10011)  = 3
f(0b10011)   =>       1  + f(0b1001)   = 3
f(0b1001)    =>       1  + f(0b100)    = 2
f(0b100)     =>       0  + f(0b10)     = 1
f(0b10)      =>       0  + f(0b1)      = 1
f(0b1)       =>       1  + f(0b0)      = 1
f(0b0)       => 0                      = 0

We run b through this function and divide the result by 2, and there is our answer.

Oracle SQL 11.2, 206 bytes
WITH v AS(SELECT b,MIN(p)i,MAX(p)a FROM(SELECT SUBSTR(TRANSLATE(:1,'])>}','[(<{'),LEVEL,1)b,LEVEL p FROM DUAL CONNECT BY LEVEL<9)GROUP BY b)SELECT COUNT(*)FROM v x,v y WHERE x.i<y.i AND x.a<y.a AND y.i<x.a;

Un-golfed :
WITH v AS( -- Compute min and max pos for each bracket type
           SELECT b,MIN(p)i,MAX(p)a
           FROM   ( -- replace ending brackets by opening brakets and split the string
                    SELECT SUBSTR(TRANSLATE(:1,'])>}','[(<{'),LEVEL,1)b,LEVEL p
                    FROM DUAL
                    CONNECT BY LEVEL<9
                  )
           GROUP BY b
         )
SELECT COUNT(*)
FROM   v x,v y
WHERE  x.i<y.i AND x.a<y.a AND y.i<x.a -- Apply restrictions for interlocking brackets