Count occurrences of an integer [closed]

Based on the question How many positive integers < 1,000,000 contain the digit 2?. I'm looking for the most creative solution to count all the Integers from X to Y containing the Integer Z. Z can be from 0 to Y.

Every found Integer only counts once, even if the integer Z appears more often. For example:

Z = 2
123 counts 1
22222 also counts 1


I will start with a really simple algorithm written in Java (because it's beloved by everyone):

public class Count {
public static void main(String[] args) {
int count = 0;
for (int i = Integer.parseInt(args[0]); i <= Integer.parseInt(args[1]); i++) {
if (Integer.toString(i).contains(args[2])) {
count++;
}
}
System.out.println(count);
}
}


if you run this with

java -jar Count.jar 0 1000000 2


you get this as the result:

468559


Because this problem is not hard to solve it's just a . Most upvoted answer posted by 28th of February wins!

closed as too broad by Dennis♦Nov 3 '16 at 17:52

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• It's not entirely clear from your post, but I guess Z can be between 0 and inf? Or just between 0 and 9? – mmumboss Feb 10 '14 at 11:21
• Z can be between 0 and Y. It doesn't make sense that Z can be bigger than Y. – Obl Tobl Feb 10 '14 at 11:31
• @OblTobl Do you really want to explicitly exclude the Z>Y case? Why not just have expected output in that case be 0? – Cruncher Feb 10 '14 at 16:14
• @Cruncher i don't mind! but it's a little bit useless i think ;-) – Obl Tobl Feb 10 '14 at 16:24
• Does this mean that N can be 123 and it would only match if the substring 123 exists? – Populus Feb 10 '14 at 16:40

bash (20)

seq $1$2|grep -c $3  Usage $ bash count.sh 0 1000000 2
468559

• it's funny if the call is longer than the program itself ;-) – Obl Tobl Feb 10 '14 at 16:33

Funciton

As usual, since the line height added by StackExchange breaks up the lines, consider running $('pre').css('line-height',1) in your browser console to fix that. Unlike my other Funciton answers, this one does not use any function declarations. It’s just a program. It uses a lambda expression, though — a feature I added to Funciton in December :) Expects the input as three decimal integers (can be negative) separated by spaces (i.e. x y z). In fact, z can be any string; for example, it could be just the minus sign (−, U+2212) to count the number of negative numbers in the interval :)  ┌───╖ ┌───┬─┤ ♯ ╟──────────┐ │ │ ╘═══╝ ╔════╗ ┌─┴─╖ ┌────╖ ╔═══╗ ┌─┴─╖ └────┐ ║ 21 ║ │ × ╟─────────────┤ >> ╟─╢ ║ ┌─┤ ʃ ╟───┐ │ ╚══╤═╝ ╘═╤═╝ ╘═╤══╝ ╚═══╝ │ ╘═╤═╝ │ └──┐ └─────┘ ┌───────────┐ │ │ ╔═╧═╗ ┌─┴─╖ ┌─┴─╖ ╔════╗ ┌─┴─╖ ┌───╖ ├─┴────────┐ │ ║ ╟─┤ · ╟─┤ ʘ ╟─╢ 32 ╟─┤ · ╟───┤ ʘ ╟─┘ │ │ ╚═══╝ ╘═╤═╝ ╘═══╝ ╚════╝ ╘═╤═╝ ╘═╤═╝ ┌─────┐ │ │ └───────┐ ╔═══╗ ┌─┴─╖ │ ┌─┴─╖ │ │ │ ┌───────────┐ └──╢ 0 ╟─┤ ʃ ╟─┐ │ │ ♯ ║ │ │ │ │ ┌───╖ ┌─┴─╖ ╚═══╝ ╘═╤═╝ │ │ ╘═╤═╝ ┌─┴─╖ │ │ │ ┌─┤ ♯ ╟─┤ ╟─┬─┐ ╔════╗ │ ┌─┴─╖ │ │ ┌─┤ × ║ │ │ │ │ ╘═══╝ └─┬─╜ └─┘ ║ −1 ║ └─┤ · ╟─┴───┘ │ ╘═╤═╝ │ │ │ │ ┌────┴────┐ ╚══╤═╝ ╘═╤═╝ │ ╔═╧══╗ │ │ │ │ │ ┌───╖ ┌─┴─╖ ┌─┴─╖ ┌───┴─────╖ │ ║ 21 ║ │ │ │ │ └─┤ ♯ ╟─┤ ? ╟─┤ = ║ │ str→int ║ │ ╚════╝ │ │ │ │ ╘═══╝ ╘═╤═╝ ╘═╤═╝ ╘═╤═══════╝ │ ┌────╖ │ │ │ │ ╔═══╗ ┌─┴─╖ └─┐ ┌─┴─╖ └─┤ >> ╟─┘ │ │ │ ║ 0 ╟─┤ ? ╟─┐ └─┤ · ╟───┐ ╘═╤══╝ │ │ │ ╚═══╝ ╘═╤═╝ └─┐ ╘═╤═╝ └───┐ ┌─┴─╖ │ │ │ ┌─┴─╖ └─┐ ┌─┴─╖ └───┤ ʘ ║ │ │ └────────────┤ · ╟─┐ └─┤ ≤ ║ ╘═╤═╝ │ │ ╘═╤═╝ │ ╘═╤═╝ ┌─────────╖ │ │ │ ╔═══╗ ╔═╧═╕ │ └─┬─┤ int→str ╟─┘ │ │ ║ 0 ╟─╢ ├─┤ │ ╘═════════╝ │ │ ╚═══╝ ╚═╤═╛ └─────────┘ │ └────────────────┴─┐ │ │ ┌─────────╖ ┌─┴─╖ ┌─┐ ┌────┴────╖ └────┤ str→int ╟───┤ ╟─┴─┘ │ int→str ║ ╘═════════╝ └─┬─╜ ╘════╤════╝ └──────────────┘  • That's pretty cool! Using a language you made yourself – pcnThird Feb 11 '14 at 2:50 • @pcnThird: I think Timwi spends all his time either golfing or creating languages in which to golf (see also Sclipting)! – Gabe Feb 12 '14 at 6:15 C# public class Program { public static void Main(string[] args) { Console.WriteLine(Enumerable.Range(Convert.ToInt32(args[0]), (Convert.ToInt32(args[1]) + 1) - Convert.ToInt32(args[0])).Count(x => x.ToString().Contains(args[2]))); } }  Example count.exe 0 1000000 2 468559  • clever solution! i like it that you did it without a loop. – Obl Tobl Feb 10 '14 at 14:53 • @OblTobl without a visible loop. – Justin Feb 10 '14 at 18:39 • of course, nice anyways – Obl Tobl Feb 10 '14 at 18:41 • It has a bug, .Range accepts (int start, int count), not (start, end). I always fall into this trap myself :) – Grozz Feb 10 '14 at 21:57 • Serves me right for quickly knocking this up in Notepad... I've tweaked the code so it is now correct! – Mo D Feb 10 '14 at 22:38 APL (29) {+/∨/¨(⍕⍺)∘⍷¨⍕¨⊃{⍺+0,⍳⍵-⍺}/⍵}  This is a function that takes Z as the left argument and the interval [X,Y] as the right argument:  2 {+/∨/¨(⍕⍺)∘⍷¨⍕¨⊃{⍺+0,⍳⍵-⍺}/⍵} 0 1e6 468559 0 {+/∨/¨(⍕⍺)∘⍷¨⍕¨⊃{⍺+0,⍳⍵-⍺}/⍵} 0 1e6 402131 42 {+/∨/¨(⍕⍺)∘⍷¨⍕¨⊃{⍺+0,⍳⍵-⍺}/⍵} 0 1e6 49401  • not really clear...but really cool! – Obl Tobl Feb 10 '14 at 15:02 Python 2.7 Need for Speed Explanation Implementation def Count(lo,hi,key): if hi == 0: return 0 # Count(lo,hi,key) = Count(0,hi,key) - Count(0,lo - 1,key) if lo != 0: return Count(0, hi, key) - Count(0, lo - 1, key) # Calculate no of digits in the number to search # LOG10(hi) may be a descent trick but because of float approximation # this would not be reliable n = len(str(hi)) - 1 # find the most significant digit a_n = hi/10**n if a_n < key: count = a_n*(10**n - 9**n) elif a_n > key: count = (a_n - 1)*(10**n - 9**n) + 10**n else: count = a_n*(10**n - 9**n) + 1 if hi % 10**n != 0: if a_n != key: return count + Count(0, hi%10**n, key) else: return count + hi%10**n else: return count  Demo In [2]: %timeit Count(0,123456789987654321,2) 100000 loops, best of 3: 13.2 us per loop  Comparison @Dennis $ \time -f%e bash count.sh 0 1234567 2
585029
11.45


@arshajii

In [6]: %timeit count(0,1234567,2)
1 loops, best of 3: 550 ms per loop

• This is, of course, much faster, but it doesn't fulfill the question's requirements. key can be any integer, not digit, between lo and hi. – Dennis Feb 11 '14 at 17:31
• there is still a mathematical solution, though it would be even longer... – Red Alert Feb 11 '14 at 22:46

Python 2.7

A solution using regular expressions:

>>> from re import findall as f
>>> count=lambda x,y,z:len(f('\d*%d\d*'%z,str(range(x,y+1))))
>>>
>>> count(0,1000000,2)
468559

• You can use re.findall in a one-liner by doing __import__('re').findall('\d... – SimonT Feb 11 '14 at 3:43

bash - 323117 14 characters + length of X, Y and Z

Thanks to devnull for suggesting seq!

seq [X] [Y]|grep -c [Z]


e.g. X = 100, Y = 200, Z = 20

$seq 100 200|grep -c 20 2  e.g. X = 100, Y = 200, Z = 10 $ seq 100 200|grep -c 10
11


e.g. X = 0, Y = 1000000, Z = 2

$seq 0 1000000|grep -c 2 468559  • nice and clear one! – Obl Tobl Feb 10 '14 at 14:53 • Why use echo when you could use seq and reduce the length by 4 characters? (1 for length of command, 2 for being able to omit curly braces and 1 for replacing .. with a single space) – devnull Feb 10 '14 at 16:21 • @devnull - thank you, and can also get rid of xargs and wc - and it also runs much faster! – Yimin Rong Feb 10 '14 at 17:22 PHP Nothing original, just celebrating my first post here. <?php$x = $argv[1];$y = $argv[2];$z = $argv[3];$count = 0;

do
{
if (!(strpos($x,$z) === false))
$count++;$x++;
} while ($x <=$y);

echo $count; ?>  Input php script.php 0 1000000 2  Output 468559  Scala: args(0).toInt to args(1).toInt count (_.toString contains args(2)) Ruby This is a great example to use reduce! puts (ARGV[0]..ARGV[1]).reduce(0) { |c, n| n.to_s.include?(ARGV[2].to_s) ? c + 1 : c }  Input: ruby script.rb 0 1000000 2  Output: 468559  Python golf - 61 f=lambda x,y,z:len([i for i in range(x,y)if str(z)in str(i)])  Python non-golf def f(x, y, z): c = 0 for i in range(x, y): c += str(z) in str(i) return c  Java8 Using the new IntStream stuff, this becomes essentially a one liner, if you ignore the obligatory Java Framework stuff: import java.util.stream.IntStream; public class A{ public static void main(String[] args){ System.out.println(IntStream.rangeClosed(Integer.parseInt(args[0], Integer.parseInt(args[1])).filter(x -> ((Integer)x).toString().contains(args[2])).count()); } }  It can be run here, although I did have to hardcode the values. • Really interesting Java solution – Obl Tobl Feb 10 '14 at 20:36 F# This solution uses IndexOf to search the string, then a little bit of number fiddling to convert the result to 1 if found, and 0 if not found, then sums the result: let count x y (z : string) = [ x .. y ] |> Seq.sumBy(fun n -> min 1 (n.ToString().IndexOf z + 1))  And it can be called like this: count 0 1000000 "2" // 468559  Regular Expression Following will count 1's digits up to 49. #!/bin/bash echo "12313451231241241111111111111111111111111111111111111" |\ sed "s/[^1]//g;s/11111/5/g;s/1111/4/g;s/111/3/g;s/11/2/g;s/555555555/45/g;s/55555555/40/g;s/5555555/35/g;s/555555/30/g;s/55555/25/g;s/5555/20/g;s/555/15/g;s/55/10/g;s/54/9/g;s/53/8/g;s/52/7/g;s/51/6/g;s/50/5 /g;s/40/4/g;s/30/3/g;s/20/2/g;s/10/1/g"  R 23 25 27chars Just get the right tool for the job. Simple use of grep in R, nothing fancy. This is what it does: grep all instances of 2 in the vector 0 until 10e6 and count the number of results using length. length(grep(2,0:100000,value=TRUE)) length(grep(2,0:10e6))  Result: [1] 468559 Offcourse you can write a function that takes the numbers as an input, just like it is shown in the example. count = function(x=0, y=1000000, z=2){ length(grep(z,x:y)) }  Now you can call count with with x, y and z, if unset (that is by default), the values for x, y and z are 0, 1000000 and 2 respectively. Some examples: count() [1] 468559  or count(20, 222, 2) [1] 59  or count(0, 100, 10) [1] 2  Some here think time is of importance, using this function in R takes around 1 second. system.time(count()) user system elapsed 0.979 0.003 0.981  • maybe it's quite too short ;-) – Obl Tobl Feb 10 '14 at 16:23 • Well, this is not code-golf anyway :) I wonder: what would the program look like if it had to take the numbers as input (rather than hardcoding them)? – Timwi Feb 11 '14 at 0:53 • Created a function for the unimaginative ;) – CousinCocaine Feb 11 '14 at 8:04 JavaScript (ES6), 63 f=(i,j,n)=>{for(c=0;i<=j;!~(''+i++).indexOf(n)?0:c++);return c}  Usage: f(0, 1e6, 2) > 468559  Un-golfed: f = (i,j,n) => { for( // Initialize the counter. c=0; // Iterate through all integers. i<=j; // Convert current number into string then increment it. // Check if the digit appears into the current number. !~(''+i++).indexOf(n) // Occurence not found. ? 0 // Occurence found. // Add 1 to the counter. : c++ ); return c }  Ruby Basically I took Pablo's answer and semi-golfed (38 chars if you drop unnecessary whitespace) it into a not-so-great example of using select. It selects every index in the range (x .. y) that contains z. This intermediate result is unfortunately stored in an array, whose size is then returned. x,y,z =$*
p (x..y).select{ |i| i[z] }.size


It looks pretty neat both syntactically and semantically, although the i[z] part doesn't really seem to make sense.

It works because x and y actually are strings, not numbers! Thus each i is also a string, and i[z] of course checks if the string z is contained in i.

$ruby count-digits.rb 100 200 20 2$ ruby count-digits.rb 0 1000000 2
468559


Python 2.7, 70 signs

f = lambda x,y,z: sum(map(lambda x: str(z) in str(x), range(0, y+1)))

>>> f(0, 1000000, 2)
468559


Shorter, 65 signs

g = lambda x, y, z: sum(str(z) in str(i) for i in range(0, y+1))
>>> g(0, 1000000, 2)
468559

• I don't think you need range(0,y+1) if range(y+1) does the same thing. Also, you can remove most of those spaces if you're golfing... – SimonT Feb 11 '14 at 3:46

Using Ruby's Enumerable#grep:

start, stop, target = $* p (start..stop).grep(Regexp.new target).size  T-SQL If I can assume variables @X, @Y, and @Z are available: With an (arbitrarily large ;) existing numbers table - 65 select count(*)from n where n>=@X and n<=@Y and n like '%'+@Z+'%'  With a recursive CTE - 127 with n(n)as(select @X union all select n+1 from n where n<@Y)select count(*)from n where n like'%'+@Z+'%'option(MAXRECURSION 0)  If the variables need to be defined explicitly: Add 58 to both answers -- Numbers table: 123, Recursive CTE: 185 declare @X int=0;declare @Y int=100;declare @Z varchar(30)='2';  I have no idea how much memory the recursive CTE can use, but it's certainly not going to win any speed contests. The example of searching for 2 in 0 to 1000000 takes 8 seconds on my system. Here's a SQL Fiddle if anyone wants to play with it. The 1000000 query takes 30+ seconds to run. • not fast but very creative! – Obl Tobl Feb 10 '14 at 19:02 Rebol ; version 1 (simple loop counting) count: func [x [integer!] y [integer!] z [integer!] /local total] [ total: 0 for n x y 1 [if found? find to-string n z [++ total]] total ] ; version 2 (build series/list and get length) count: func [x [integer!] y [integer!] z [integer!]] [ length? collect [for n x y 1 [if find to-string n z [keep true]]] ]  Usage example in Rebol console (REPL): >> count 0 1000000 2 == 468559  PowerShell Two solutions, both 40 37 chars. For all versions of PowerShell: $a,$b,$c=$args;($a..$b-match$c).count


PowerShell V3 and up have the sls alias for Select-String. This requires the @ to force an array if only one value makes it through the pipeline.

$a,$b,$c=$args;@($a..$b|sls $c).count  Batch @setLocal enableDelayedExpansion&@set a=0&@for /L %%a in (%1,1,%2) do @set b=%%a&@if "!b:%3=!" NEQ "!b!" @set/aa+=1 @echo !a!  H:\uprof>count 0 1000000 2 468559 H:\uprof>count 1 2 3 0  A bit more readable - @setLocal enableDelayedExpansion @set a=0 @for /L %%a in (%1,1,%2) do ( @set b=%%a @if "!b:%3=!" NEQ "!b!" @set/aa+=1 ) @echo !a!  Nice and simple. Uses string manipulation to check if the variable !b! is the same as itself without the third user input, %3 (!b:%3=!). Mathematica First way: strings x, y, z are converted to strings. If a string-integer is not free of z, it is counted. f[{x_,y_},z_] :=Length[Select[ToString/@Range[Max[x, z], y], !StringFreeQ[#, ToString@z] &]]  Examples f[{22, 1000}, 23] f[{0, 10^6}, 2]  20 468559 Second way: lists of digits g[{x_,y_},z_]:=(t=Sequence@@ IntegerDigits@z;Length@Cases[IntegerDigits@Range[190], {s___,t,e___}])  Examples g[{22, 1000}, 23] g[{0, 10^6}, 2]  20 468559 • Mathematica is always fascinating, even for simple problems – Obl Tobl Feb 10 '14 at 19:26 GolfScript I've been trying to improve my GolfScript skills so I thought I'd give it a shot with this question. Here's what I came up with: @@0\{.3$>}{.4$?-1>@+\(}while@;;\;  This can be broken down like this: 0 1000000 2 # parameters @@ # convert Z to string and put at bottom of stack 0\ # init counter and swap {.3$>}         # loop condition: Y > X
{              # loop body
.           # convert to string
4$? # search for substring -1>@+ # if found add to counter \( # decrement Y } # end loop body while # perform loop @;;\; # cleanup  Even though it's GolfScript, by goal was more to try to make it relatively efficient rather than compact, so I'm sure that someone can point out various ways this can be improved. Demonstration: Note that I've reduced Y in the demo so that it can complete in < 5 seconds. PHP - 112 No visible loops, but a bit heavy on memory! <?=count(array_filter(range($argv[1],$argv[2]),function($i)use($argv){return strpos($i,$argv[3].'')!==false;}));  Usage php script.php 0 1000000 2 ECMAScript 3 to 6 (javascript, JScript, etc) using regex: function f(x,y,z,r){for(r=0,z=RegExp(z);x<y;r+=+z.test(''+x++));return r}  breakdown: function f(x,y,z,r){ // note argument r, eliminating the need for var  for( r=0, z=RegExp(z) // omitting new since ES will add it if omitted ; x<y // ; r+=+z.test(''+x++) // x++ == post increment // ''+Number == convert Number to string // test gives true | false // +Boolean converts boolean to 1 | 0 // r+=Number incrementing r (were Number is always 1 or 0) ); // no body thus semicolon is mandatory! return r; // returning r }  using indexOf: function f(x,y,z,r){for(r=0;x<y;r+=+!!~(''+x++).indexOf(z));return r}  breakdown: function f(x,y,z,r){ // note argument r, eliminating the need for var  for( r=0 // omitting new since ES will add it if omitted ; x<y // ; r+=+!!~(''+x++).indexOf(z) // x++ == post increment // ''+Number == convert Number to string // indexOf returns index or -1 when not found // !!~ indexOf converts sentinel value to boolean // +Boolean converts boolean to 1 | 0 // r+=Number incrementing r (were Number is 1 or 0) ); // no body thus semicolon is mandatory! return r; // returning r }  this function-body is one char less then florent's, so when using ES6 => function notation the total would be 62 char Example call: f(0,1e6,2) Example use: alert( f(0,1e6,2) ); JSFiddle here PS: both functions above return their local variable r. So when leaking the result variable r into the global scope, one can again save 10 characters: function f(x,y,z){for(r=0;i<=j;r+=+!!~(''+i++).indexOf(z));}  Example use: alert( f(0,1e6,2)||r ); Delphi - 120 Bit to much for my taste, going to see if i can get some off. var x,y,z,i,c:int16;begin readLn(x,y,z);for i:=x to y do if inttostr(i).contains(inttostr(z))then inc(c);writeln(c);end.  • don't mind for the length, i love to see a delphi solution ;-) – Obl Tobl Feb 11 '14 at 8:45 • @OblTobl Great, but its so much fun to try make it short :P – Teun Pronk Feb 11 '14 at 8:45 Python 2.7 - 50 chars Bit of a saving on the existing Python answers. lambda x,y,z:sum(1for n in range(y-x)ifz+xinn)  Using the following tricks: • Sum can be applied to a generator, unlike len, so use sum(1...) instead of len([n...]) • Use  instead of str(), which also allows... • Kill all spaces - see '1for' and 'ifz+xinn' • Remove the first range() arg by starting at 0 and testing the offset (actually...saves me nothing but I like the look of it better :) ) In action: In [694]: (lambda x,y,z:sum(1for n in range(y-x)ifz+xinn))(0,1000000,2) Out[694]: 468559  k [28 chars] {+/($x+!y)like"*",$:[z],"*"}  Usage {+/($x+!y)like"*",$:[z],"*"}[0;1000000;2] 468559  • You can save a character by replacing $:[z] with (\$z). – mollmerx Feb 11 '14 at 18:57
• However, the upper bound of your solution is incorrect. It enumerates from x to x+y-1, not from x to y. – mollmerx Feb 12 '14 at 14:50