1. Write a program that shows the amount of 0's in a given

>>57158170
is this your assignment ?

>>57158176
Yes

Since there doesn't seem to be any bird threatening my existance I fail to see my motivation for writing it.

>>57158188
what language do you have to use ? C ?

>>57158170
What language is your homework answer supposed to be written in?

>>57158170

function iloveponies() { seq -s '' $1 $2 |sed -nr 's/[^0]//gp' |tr -d '\n' |wc -c; }

Usage:

iloveponies 100 200
22

>>57158213
Preferably C

>>57158170
Turn each number into a string
Look for 0's with substring
If there is one. int++

>>57158240
Performance wise, this isn't the most optimal solution.

>>57158252
Wrong result.
This is what happens when you let Python users try to "solve" something :^)

Correct, one line of GNU coreutils:
>>57158220

>>57158170
Since you probably won't be using ruby in class, and won't be able to translate it if you can't figure it yourself.... sure!

c=0
100.upto(200).each{|i|i.to_s.split(//).each{|j|c+=1 if j=="0"}}

>>57158264
>This is what happens when you let Python users try to "solve" something :^)
I was trying to show off and misread OP. I have deleted the message so clearly this never happened

>>57158285
kys

>>57158275
>>57158252
>>57158220

not the most elegant, anyone has a pure math solution?

>>57158275
And yes. That's horribly inefficient runtime, but was the quickest to tap out on my phone.

>>57158307
I do have it in C, give me a second

>>57158317
Don't. OP should do his own homework.

>>57158307
This
How about doing it in base 28. Or a variable base, for that matter. That way you couldn't do those string conversions

>>57158317
not the most elegant by all means of course, but pure math

>>57158323
You can do string conversions in any base.

>>57158307
Pure math solution is difficult and base dependant (I think). Especially if you don't want to loop or refuse. My number theory is a bit rusty, so I could be dead wrong.

>>57158302
Not before redeeming myself

sum([str(i).count("0") for i in range(100, 201)])

>>57158337
Most langages lack standard conversions for bases other than 2/8/10/16/64 though

int r(int a){
if(a<=0)
return 0;
else{
if(a%10==0)
return 1+r(a/10);
else return r(a/10);
}
}

int main(){
int i=100, sum=0;
for(i=100;i<=200;i++){
sum+=r(i);
}
printf("%d", sum);

File: cap.png (2KB, 261x68px) Image search: [Google]

2KB, 261x68px

Here you go
http://pastebin.com/nXSKUid

>>57158323
One of the lovely things in ruby, is that int to string amd string to int can take base as optional parameter.

Damnit! I don't have Haskell on my phone, and left my laptop today.

>>57158357
itoa does it in C. I don't think I can name a single language that does not have integer to string with arbitrary base conversion.

>>57158385
Sure that base parameter is without limitations?

>>57158398
You should read the documentation again
>base
>Numerical base used to represent the value as a string, between 2 and 36, where 10 means decimal base, 16 hexadecimal, 8 octal, and 2 binary.
Might give you the 28 but not 37/64/bases where one byte doesnt even fit in one char

>>57158379
http://pastebin.com/nXSKUidg

function zerocast(x1, x2)
  xs = [x1:x2];
  n = size(xs, 1);
  zs = 10 .^ [1:7];
  zms = zs ./ 10;
  incmat = zeros(size(xs, 1), 7);
  mks = n - [0:n-1];
  for(iter = 1:7)
    ibool = mod(xs, zs[iter]) == 0;
    incmat[ibool, iter] = minimum(zms[iter], mks[ibool]);
    end;
  return sum(incmat);
  end;

>>57158440
>Most langages lack standard conversions for bases other than 2/8/10/16/64 though

Your statement is incorrect.

>>57158465
Then let me refine it
Most languages lack standard conversions for other bases than [2,64] though

autism

>>57158510
thank's for the compliment

from collections import Counter

def counterThing(start:int,end:int):
  if all(map(lambda n:type(n)==int, (start,end))):
    return Counter(str(list(range(start,end+1))))['0']
  else:
    raise TypeError("u dun fucked up fuckface")

>>57158195
This, if a murderous crow was staring me down with a knife I would have already written the program.

>>57158440
I've played with it before, and found several, but it does do many seemingly arbitrary bases I didn't expect it to (3 and 20 come to mind)

File: 1470533779993.jpg (29KB, 412x430px) Image search: [Google]

29KB, 412x430px

>>57158538
DO MY BIDDING

>>57158264
>Correct, one line of GNU coreutils:
Works fine with busybox too.

#include <stdio.h>
main()
{
printf("22");
}

Are you guys fucking stupid?

File: 5391590i.jpg (107KB, 620x586px) Image search: [Google]

107KB, 620x586px

>>57158170

> let f = ((length . filter (=='0') . concatMap show) .) . enumFromTo 
> f 100 200
22

Fuck efficiency

function zero(start, end) {
    if (!start || !end) return 'no'
    let counter = 0
    while(start < end) {
        if (start.toString().indexOf(0)) counter += --start.toString().split('0').length
        start++
    }
    return counter
}

honestly haven't fired up dev since last year

#include <iostream>
using namespace std;

int main()

{
    int a, b, x=0, z=1;
    cin >> a >> b;
    
    for (int i=a; i<=b; i++)
    {
        z=i;
        while (z!=0)
        {
            if (z%10==0) x++;
            z/=10;
        }
    }
    
    cout << x;
    return 0;
}

using type conversion would be easier

void ZeroOutputter(int start, int end,int tens,int noof0s){ // tens default will be 0, this can only have the end range modified sadly. starts default will be 0 as well.
    if (start != end){
        if ((start / 10) == tens){
            ++noof0s;
            ++tens;
        }
        
        ++start;
        ZeroOutputter(start, end, tens, noof0s);
    }
}

>>57158170

#include <iostream>
#include <stdlib.h>
#include <stdio.h>

//--------------------------------------------
//You class definition here
//--------------------------------------------

int main()
{
You you;

return you.do_your_fucking_homework();
}

>all of these fags doing muh brute force poogramming
Trying to find an actual function to compute it is more fun.

>>57158170
>public static void range(int a, int b) {
> if (a == 100 && b == 200) return 22;
> throw new RuntimeException();
>}

>>57158712
>Trying to find an actual function to compute it is more fun.
no

>>57158170
For Arduino: blinkxtimes.ino

/*
  Blink Zeros In Range
  Turns on an LED on for one second, then off for one second, repeatedly
  according to the number of zeros in a range
 
  This example code is NOT in the public domain. DO NOT STEAL IT.
 */
 
// Pin 13 has an LED connected on most Arduino boards.
// give it a hj:
int led = 13;

// the setup routine runs once when you press reset:
void setup() {                
  // initialize the digital pink as an output.
  pinMode(led, OUTPUT);  
  blinkXTimes(zerosInRange(10,20));
}

// the loop routine runs over and over again forever:
void loop() {

}

void blinkXTimes(int xtimes)
{
  for(int x=1; x<=xtimes; x++)
  {
    digitalWrite(led, HIGH);   // turn the LED on (HIGH is the voltage level)
    delay(100);               // wait for a second
    digitalWrite(led, LOW);    // turn the LED off by making the voltage LOW
    delay(100);               // wait for a second  
  }
}

int zerosInRange(int a, int b)
{
  String d;
  int  f;
  
  for (int c=a; c<=b; c++)
  {
    d=String(c);
    for(int e=0; e<=d.length()-1; e++)
    {
       if(d.charAt(e)=='0')
        f++; 
    }
  }
  return f;
}

>>57158776
>String
>c
???

>>57158723
kek

>>57158757
>lol i'll just iterate through the numbers as strings like literally everyone before me has done ;^)
>but get this! I'll do it in language y!!!
kys
Why settle for linear run time when there's in all likelihood a constant run time version.

(defun zeroes-in-range (a b)
  (loop for i from a to b
     sum (count #\0 (format nil "~d" i))))

Plebs using string conversion

fn main() {
    println!(
        "Amount of numbers containing 0 between 100 and 201: {:#?}",
        (100..201).map(|x| amount_of_zeros(x)).sum::<i32>()
    );
}

// Pure arithmetic implementation. Uses the fact that numbers divisible by 10 end with a 0
fn amount_of_zeros(mut n: i32) -> i32 {
    let mut x = 0;
    while n > 9 {
        if n % 10 == 0 {
            x += 1;
        }
        n = n / 10;
    }
    if n == 0 {
        x += 1;
    }
    x
}

>>57158307

2*(20 - 10) / 10=2
2*((200 - 100) / 10 + (200 - 100) / 100)=22

// Maybe something like this could work?
2*((2000 - 1000) / 10 + (2000 - 1000) / 100) + (2000 - 1000) / 1000))=222

>>57158220
>>57158240
>>57158275
>>57158356
>>57158596
>>57158633
>>57158776
Plebs

File: 1410827289627.jpg (12KB, 380x250px) Image search: [Google]

12KB, 380x250px

>>57158170
>>57158170
>tfw half the girls in your school are nerdy qts like this
>too spaghetti to talk to any of them
Just end my fucking life fampai

Just a reminder that if you can't do this in a single line of code your language of choice is shit

>>57158170
Just use modulo 10

This is solvable in O(1), involves a formula I can't quite remember.

>>57159187
>implying single line answers are more readable than different functions

>>57158170
sup triggu

>>57159200
I remember it
10+12=22
Done.

>>57159211
Nah, it was way more general, for any n between 1 and 1000000000 ... but anyways, here's the trivial solution: http://ideone.com/tEnGNh

I'm at 34 now, anyone got something shorter?

say~~(()=join('',100..200)=~/0/g)

>>57159317
>le perl programmer fighting over who can write the most unreadable program

kek

>>57159317
Make it general. Otherwise say 22 is shorter.

>>57159317
>>57159345
>most unreadable
Nah, I can obfuscate it much further

This is the shortest I got

It's not even that unreadable

>say
print with newline, 2 chars shorter

>~~
Forces scalar context, when you print an array in scalar context it prints it's length

print 0+(1,2,3)

will print 3

>() =
Force list context for the regex

>join
Joins the elements of a list to a string with the specified seperator ('', i.e. none)

>100..200
range

>=~/0/g
Match all the appearances of 0

>>57159383
Thanks, forgot about it
It's 31 btw, I forgot to generalize it and wc counts the newline too

say~~(()=join('',<>..<>)=~/0/g)

File: resized_lizard-meme-generator-aww-yiss-fc8115.jpg (24KB, 800x744px) Image search: [Google]

24KB, 800x744px

>>57158776
I like the cut of your jib.

>>57159447
chopped it down to 28 las

say~~+join('',<>..<>)=~y/0//

function zerocount(r::UnitRange{Int64})
    zeroes = 0
    for i in r
        for l in string(i)
            if l == '0'
                zeroes += 1
            end
        end
    end
    return(zeroes)
end

This boring shit is faster than anything else I can conjure up.

>>57158776
stolen :^)

>>57159508
27

say~~join('',<>..<>)=~y/0//

countzero :: Int -> Int -> Int

countzero lower upper = sum [foldl (\acc x -> if (x == '0') then (acc + 1) else (acc)) 0 (show x) | x <- [lower..upper]]

>>57159511
Julia?

>>57159578
yes

Finally, a superior C version (probably someone smarter than me can still manage to trim off a couple characters while staying under 80 character lines):

#include <stdlib.h>
#include <stdio.h>
z(int n){return !n?0:z(n/10)+!(n%10);}main(int r,char **v){int a=atoi(v[1]);
int c=!a;while(a<=atoi(v[2])){c+=z(a);a++;}printf("%d\n",c);}

Usage:

$ gcc count_zeroes.c -o count_zeroes
$ ./count_zeroes 100 200
22

>>57159634
Forgot to mention, this does assume base 10, but is at least pure math, without using string bullshit beyond trusty old atoi.

>>57159634
>>57159650
nice

>>57159634
Managed to shorten it some more:

#include <stdio.h>
int atoi(char *c);z(n){return !n?0:z(n/10)+!(n%10);}main(int r,char **v){int a=
atoi(v[1]);int c=!a;while(a<=atoi(v[2])){c+=z(a);a++;}printf("%d\n",c);}

Can somebody do it in Java?

void main(string[] args)
{
    import std.range: iota;
    import std.conv: to;
    import std.algorithm;
    import std.stdio: writeln, writefln;

    if (args.length != 3) {
        "Usage: %s <from> <to>".writefln(args[0]);
        return;
    }

    iota(to!int(args[0]), to!int(args[1]) + 1)
        .map!(n => to!string(n).count("0"))
        .sum
        .writeln;
}

>>57159737
Err should be args[1] and args[2] in iota.

>>57158170
Who is this semen demon?

the laziest and dirtiest solution in C++

void ZeroOutputter(int start, int end,int noof0s){
    if (start != end){
        string val = to_string(start); // to string converts int to string
        string::iterator itr = val.begin();
        while (itr != val.end()){
            if (*itr == '0'){
                ++noof0s;
            }
            itr++;
        }
        ++start;
        ZeroOutputter(start, end, noof0s);
    }
    else{
        string val = to_string(start); // to string converts int to string
        string::iterator itr = val.begin(); // does final part
        while (itr != val.end()){
            if (*itr == '0'){
                ++noof0s;
            }
            itr++;
        }
        cout << noof0s << endl;
    }
}

>>57159737
Jesus christ, plebs and their retarded string functions. Here's how a real man counts zeroes in an int (should work in Java or C):

int count_zeroes(int n) {
  if (n == 0) return 1;
  return count_zeroes_recursive(n);
}

int count_zeroes_recursive(int n) {
  int z = (n % 10) == 0 ? 1 : 0;
  return n == 0 ? 0 : z + count_zeroes_recursive(n / 10);

On another note, a version of >>57159704 that compiles with no warnings:

#include <stdio.h>
int atoi(char *c);int z(int n){return !n?0:z(n/10)+!(n%10);}void main(int r,
char **v){int a=atoi(v[1]);int c=!a;while(a<=atoi(v[2])){c+=z(a);a++;}printf(
"%d\n",c);}

File: 1475294000167.jpg (65KB, 411x412px) Image search: [Google]

65KB, 411x412px

>>57159209
>mfw triggu didn't age well.
Daily reminder that mechanical keyboards and kpop make you age faster.

>>57159773

    for (const auto &c: std::to_string(start)) {
        if (c == '0')
            ++noof0s;
    }

>>57159786
a real man wouldn't be afraid to learn a new language instead of using an obsolete one

#include <iostream>

int zeroes(int n)
{
    int count = 0;
    while(n != 0) {
        if(n % 10 == 0)
            count++;
        n/=10;
    }
    
    return count;
}
int main(void)
{
    int range1, range2, count = 0;
    std::cout << "Please input your range: ";
    std::cin >> range1 >> range2;
    for(int i = range1; i <= range2; i++)
        count += zeroes(i);
    std::cout << "There are " << count << " zeroes in your range.\n";
    
    return 0;
}

rate my 1st grade C.

>>57159544
kek
p cool

>>57159844
True. But all the people using "new" languages (even ruby is over 25 now) are doing shit like converting to strings.

A 186-byte C solution isn't superior because it is faster (even though it probably is despite being very non-optimal). It's superior because it accomplishes the task using only the tools which are necessary and nothing more.

>>57159839
ah yes i have forgotten about ranged loops in C++

but i feel inadequate that a mathmatical solution eludes me, are there books to read from so I may gain insight into such solutions

>>57159906
At least two mathematical solutions have already been posted, but the easier one to read is probably >>57159849.

>>57159906
(more) effective c++ by scott myers would be a good start

>>57159899
i wouldn't call it a bad thing either though, the solution with string conversion allows people otherwise unable to solve the problem to actually provide a solution to the problem, whether the most optimal/minimal or not

>>57159849
Your zeroes function is okay, but your main function isn't C, it's C++. It's probably OK C++, though, considering C++ people generally love their overly verbose ugly-as-hell stream operators and namespace specifiers.

A for content, B- for style (I've definitely seen worse).

>>57159917
I know that, but i'd like to ask if there are books that open me up to such mathematical solutions

I have the CLRS 2nd edition if that counts, but are there any more?

>>57159929
disregard the first part of my post, i entirely misread what >>57159906 said

>>57159917
This is not really a mathematical solution >>57159849 as it is still checking every number.

def os(n):
    m = log(n)/log(10)
    sum = 0
    for j in range(int(m-1), 0, -1):
        sum += pow(10, j)
    return int(m)*pow(10, (m-1)) - sum

0s from 0 to n
Change the sum to it's closed form and it's O(1)

>>57160002
>mathematical

Rather, I should say it is not algorithmic, in some senses I guess it could be considered mathematical, however not at all efficient.

>>57159936
There isn't really anything C++ there except cin and cout, I could've used printf and scanf just as well but it's just preference really.

>>57160081
Fair enough. Why anybody typing so many extra characters just to use the C++ method for writing to a file (or stdout) is still beyond me, though.

Java beginner here, been learning for less than a month

    public static int zeroes ( int fromRange , int toRange ) {
        int zeroes = 0;
        int x = 10;
        while (x <= toRange){
            for (int i = fromRange; i <= toRange; i++){
                if (x > 99) {
                    if (i % x < 10) {
                        zeroes++;
                    }
                }
                else if (i %  x  == 0) {
                    zeroes++;
                }
            }
            x *= 10;
        }
        return zeroes;
    }

Kind of embarassed to post this but it's the best I could come up with

It seems to work

How retarded is it as a solution?

>>57160037
Better watch with your big-O notations, friend. Runtime complexity is formally defined as in relation to the length of the input, not the size of a number. Your solution is only psuedo-polynomial time. The length of the input, though, is determined not by how big you think the number is, but by the *number of digits*. As the number of digits increases linearly, the size of the number (and the runtime of your algorithm) increases exponentially. So, technically, your solution (and every solution posted so far) is O(<input base> ^ <input digits>). They'll jump all over you for this shit as a grad student in theoretical comp sci.

https://en.wikipedia.org/wiki/Pseudo-polynomial_time

>>57160179
>x=10
>if x>99
>if 100%10<10
>zeroes++;

Int a= min
Int b= max
Zeroes=0;
For(i=a;i <b;i++){
If i%10==0{
I_count=i;
While (i_count>0){
Zeroes++
I_count=i_count/10
}
}
}

If the number is an integer this seems perfectly fine.
Try this out, >>57158170

>>57159049
>muh arithmetic
what do you think int to string does m8?
you're literally reinventing the wheel.
>>57159200
Are you sure it was O(1)?
for ranges of the form 10^p to 2*10^p, where p is a positive integer the amount of zeroes is p*10^(p-1) which is O(log10(p)), because 10^(p-1) takes p operations to compute.

>>57160037
>>57160195
o k friendo
anyway here is O(1)

def test3(n):
    m = log(n)/log(10)
    return int(round(int(m)*pow(10, (m-1)) - (((1 - pow(10, int(m)))/(1 - 10)) - 1)))

Note this is for 0-n exclusive, obviously you can work out ranges using it though.

>>57160205
Whoops I should mention not to do this if your min is 0 or less, but assuming it actually is 100 like in your post it should work I think.
The min>0

>>57160221
10^(p-1) takes p operations to compute.
wow what the fugg
why are computers so fucking shit

>>57160179
I've got to admit, it's pretty tough to understand to say the least. For one, I don't think it will work if your range involves numbers above 1000. Try it with a "range" of 1010 to 1010 (you should get 2, but I bet you'll get 1).

I'd highly recommend taking a look at the "zeroes" function in >>57159849, because it should work in Java, too.

>>57160227
Nope, still pseudo-polynomial (so technically exponential) and not O(1) in any case due to >>57160281

>>57160309
>>57160309
>>57160309
>>57160309
>>57160309
STOP
It's the best solution anyway, since you can type it into a fucking calculator, unlike ebin iterative methods.

>>57160331
Oh shit, sorry I actually didn't read yours correctly. It *is* O(1)... jesus christ I'm a retard.

Still, it's incorrect. Gives the same answer for 200, 201, and 202, for example.

>>57160415
Er, need to correct this again. The thing you posted is O(log(n)), since the exponent passed to pow(...) is related to log(n). It's still incorrect because it misses some zeroes, though.

>>57160415
Theoretically speaking, there is no O(1) solution. As >>57160221 tried to explain, you'd expect the total number of zeros in the base-b representations of all integers from 1 to n to have a lower bound in o(n) (because every b-th number already has a zero).

Even if you calculate it in the most superior manner, you can't procuce an answer of length o(log n) in constant time (indeed you can't even read your input completely in any less time and I'm not sure you can compute, say, the logarithm of a number without reading it entirely).

>>57160415
How so, it calculates pow(constant, length of input). I don't think you can do pow in constant time.

Anyone solved this in O(log10(a)+log10(b))?
I don't have time but if they thread will be up later I'll come up with some solution.

>>57160505
Yeah, I corrected myself in >>57160462.

>>57160503
>you can't even read your input completely [in log(n) time]
True dat. Looks like I got out-algorithm'd

>>57159704
No need to include stdio.h, but it will warn.

>>57160503
Assume all numbers are limited to 64 bit integers, otherwise it becomes very hard to tell even the complexity of trivial functions like f(x)=x*x

>>57160281
well p-1 worst case, there are certainly some optimizations[1]. I'd assume pow implements some, but for exponents < 10 i doubt you can get below linear complexity
[1] consider 2^16
2*2=2^2
2^2*2^2=2^4
2^4*2^4=2^8
2^8*2^8=2^16
that's 4 multiplications to calculate 2^16

>>57160691
True, I could also take out the atoi prototype, too. 135 characters, but several warnings:

z(n){return !n?0:z(n/10)+!(n%10);}main(int r,char **v){int a=atoi(v[1]);int c=
!a;while(a<=atoi(v[2])){c+=z(a);a++;}printf("%d\n",c);}

>>57160691
does he need the int atoi(char *c);
if so, why

>>57160732
nevermind i guess, got ninja'd

>>57158170
>Make a sieve
>Calculate the highest power of 10 in that interval
>For each number divisible by 10^n add n zeroes and remove it from the sieve

Implement this in Python.

>>57160992
add 1, not n or you'll be counting 100 as 3 zeros because it is dividable by both 10 and 100.

>>57158170

x =0
for i in range(1,100):
    if i == 0:
        x++
print x

I haven't written anything in python in like a year but maybe it will work.

>>57161113
i guess it needs another for loop or something.

File: CkH3YRqUUAA3h1B.jpg (39KB, 600x726px) Image search: [Google]

39KB, 600x726px

>>57161113
>even considering the possibility of this working

>>57160992
how would that work for 103?
as far as i can tell you're only counting numbers with trailing zeroes

>>57160415
Oh well RIP, I only know it works for powers of 10. I just tried it on shit like 54 and 96 and it seemed to work too.

>>57161159
I know. I gave up writing code last year.

Maybe this will work?

x = 0
for i in range(1,100):
    for 0 in i:
        x++
print x

if 0 in i:
x++

?????

i dunno.

>>57161113

sum([1 for n in (''.join([str(i) for i in range(1,100)])) if n=='0'])

 
    var zeroes = function(a, b) {
        var a;
        var b;
        var num = 0;
        for (var i = a; i <= b; i += 10) {
            if(i % 10 == 0) {
                num += 2;
            }
        }
        document.write(num);
    }

    zeroes(100, 200);

Had to cheat because I'm an idiot. How would I change this to actually do it properly?

>>57161224
try learning C, that should teach you programming
Your first attempt was
"Go through all numbers from 1 to 100, if a number is 0, add 1 to your count."
In other words it goes through 1, 2 , 3, 4, 5... till 100 in that order, and check whether each number equals 0.

>>57158209
Python

def zeroes_in_range(rstart, rend)
  count = 0

  for x in (rstart..rend) do
    c = x.to_s.scan(/0/).size
    count += c
  end
  
  count
end

puts zeroes_in_range(100, 200)

>>57161321
you're only counting trailing zeroes
int zeroCount(int a)
{
int c = 0;
while(a > 0)
{
c += (a % 10 == 0); //equivalent to if(a%10==0) c++
a /= 10;
}
return c;
}

#include <stdlib.h>
#include <stdio.h>
#include <iostream>

int zeros_in_number(int number)
{
    int ret = 0;
    int aux_num = number;
    
    for(;aux_num != 0;)
    {
        if(aux_num%10 == 0)
        {
            ret++;
            
            aux_num /= 10;
        }
        else
        {
            aux_num /= 10;
        }
    }
    
    return ret;
}

int main()
{
    int a = -1;
    int b = -1;
    int zeros_counter = 0;
    
    std::cout << "Number a: ";
    while(std::cin >> a && a < 0)
    {
        std::cin.unget();
        std::cout << "Number a: ";
        std::cin >> a;
    }
    
    std::cout << "Number b: ";
    while(std::cin >> b && (a >= b || b <= 0) )
    {
        std::cin.unget();
        std::cout << "Number b: ";
        std::cin >> b;
    }
    
    for(int i = a ; i <= b ; i++)
    {
        zeros_counter += zeros_in_number(i);
    }
    
    std::cout << "\n\nTotal zeros in interval: " << zeros_counter << std::endl << std::endl;
    
    return 0;
}

 
#include <stdio.h>
#define MIN 100
#define MAX 200
int zerosfun(int);
int zeros2 = 0;

int main()
{
    for(int i=MIN;i<=MAX;i++)
    {
        zerosfun(i);
        printf("%d, %d\n", i, zeros2);
    }
    
    return 0;
}

int zerosfun(int i)
{
    if(i > 9)
    {
        if(i%10==0)
            zeros2 += 1;
        zerosfun(i/10);
    }
    else
        return zeros2;        
}
 

fuck yes

>>57158170
This sounds like something a simple for loop would take care of.

>>57158255
Who gives a shit, computers have 20 cores and 600gb of RAM nowadays.

>>57163011
That's why hiring pajeets and dev-hipsters-macfags is profitable...

>>57163011
BUT WHAT IF WE NEED TO KNOW THE CEROS FROM 1 TRILLION NUMBERS? EH?? THAT WOULD TAKE AGES AMIRITE?

REKT1!

File: 1418226836357.jpg (37KB, 251x242px) Image search: [Google]

37KB, 251x242px

getZeros :: Integer -> Integer
getZeros n
    | n == 0             = 1
    | n <= 9  || n >= -9 = 0
    | n `mod` 10 == 0    = 1 + getZeros (n `div` 10)
    | otherwise          = getZeros (n `div` 10)

zerosRange :: Integer -> Integer -> Integer
zerosRange m n = sum (map getZeros [m..n])

>using string functions

200/(100/10)+2

>>57163157
that code looks sexy as fuck

>>57163192

Yeah, and I just realized I fucked it up. The or should be an and.

>>57158240

Or you could stop being an idiot and think for 5 minutes to come up with the formula.

>>57159786
>recursion
Enjoy your stack overflow

100-200

101 digits

100 10 1
3 2 1

10c1 x 2 = 10 x 2 = 20
(100 and 200) -> 2

20 + 2 = 22

Similar to power. Too lazy to make a general case

File: small.gif (88KB, 10000x10000px) Image search: [Google]

88KB, 10000x10000px

>>57163098
>>57163011
and this attitude is why almost no GUI text editor can handle text files above a few hundred megabytes, file explorers can't handle directorys with tens of thousands of files, NTFS is slow as fuck, etc.

>>57163228
>5 minutes
i'm pretty sure we've tried for longer than that and haven't come up with a solution yet

>>57161113
>diplomaguy.png

I was going to try and make this an abhorrent abomination with a ton of lambdas

print(sum(list(map(lambda s: str(s).count('0'), list(range(100, 201))))))

>>57158170

(\x y -> sum [ length $ filter (== '0') (show a) | a <- [x..y]])

Haskal masturrace

>>57158264
>Python
That's not Python though.

>>57160518
Done.

fn stage1(mut d: i32, p: i32) -> i32 {
    let mut ret = 0;
    for i in 0..p {
        ret += d / 10 - 1;
        d /= 10;
    }
    ret
}

fn stage2(n: i32, d: i32, p: i32) -> i32 {
    (n / d - 1) * p * (d / 10)
}

fn stage3(mut n: i32, mut d: i32, p: i32) -> i32 {
    let mut ret = 0;
    n %= d;
    for i in 0..p {
        d /= 10;
        ret += (n / d + 9) / 10 * d;
        if (n / d) % 10 == 0 {
            ret += n % (d * 10) + 1;
        }
    }
    ret
}

fn zeros(mut n: i32) -> i32 {
    let mut d = 1;
    let mut p = 0;
    while d * 10 <= n {
        d *= 10;
        p += 1;
    }
    //println!("{}: {} {} {}", n, stage1(d, p), stage2(n, d, p), stage3(n, d, p));
    stage1(d, p) + stage2(n, d, p) + stage3(n, d, p) + 1
}

fn main() {
    let a = 100;
    let b = 200;
    
    println!("{}", zeros(b) - zeros(a - 1));
}

Everyone who solved it in O(n) or more should not post on /g/.
I'm sure there might be way to solve it in more nice way, but at least it works in O(log10(n)).

>>57163817
test with b= 202 please

>>57163917
24

python

>>> ''.join([str(x) for x in range(100, 201)]).count('0')

>>57163943

for i in 0..p {
        ret += d / 10 - 1;
        d /= 10;
    }

could this be written as

for i in 0..p {
        d /= 10;
        ret += d - 1;
    }

File: gif.gif (4KB, 870x58px) Image search: [Google]

4KB, 870x58px

>>57158307
>>57158353
It took me some time, but I got it. There's probably a better way, but I didn't want to bother. It involves using min(), max(), floor(), and mod() for math functions.
Let f(x,y,b)->c be a function that maps the amount of 0's between x and y in base b, and gives the result as a number, c.

Pic related is the function.

>>57164015
>constant time solution
that's really good, i didn't think that was possible.

>>57163817
what do your stages represent?

>>57164015
how do manage to create that formula

>>57164007
Thanks for help.

>>57163817
>>57164092
If anyone is wondering, I'll explain how it works.

Let's say I have number 30456
First I divide this problem into 3 smaller problems:
1) number of zeros from 1-9999 - We can notice 0 appear on first from right place 999 times, on second 99 times, etc.
2) number of zeros between 10000-29999 - For every ten thousands numbers, 0 will appear on 4 different places, 40 times each
3) number of zeros from 30000-30456 - Is a little harder.
Let's forget about ten thousand part, and focus on 0456.
0 on 4th place will appear 457 times.
0 on 3rd place will appear only in 0000 to 0099 = 100 times,
0 on 2nd place will appear in packs of 10 every 100 numbers: 0000-0009, 0100-0109, etc. = 40 times
0 on 1st place will appear every 10 numbers: 0000, 0010, 0020, etc. = 45 times

And at the end we add 1 because 0 itself is a magic number that has leading zeros.

I'm not a mathematician so I didn't prove any of these things, I just noticed these relations experimentally.

>>57164278
similiarly to how one creates algorithms. think about how to solve a problem hard enough till you come up with something.

>>57164281
>2) number of zeros between 10000-29999 - For every ten thousands numbers, 0 will appear on 4 different places, 40 times each
>40 times each
how so, there are 1000 5 digit numbers that start with 10

>>57158591
almost bud,

#include <stdio.h>
int main(){
int num = 22;
print("%d", &num);
return 0;
}

>>57164049
Thanks. I'm sure it could be cleaned up a bit, though.

>>57164278
I'll explain how it works here, since I did it in parts. I created this by testing it out in Desmos, and I created the actual points (like (0,1),(1,1), etc.) in a bash script and just copied and pasted it into Desmos to simplify it.

That first part just increases by 1 each time 10 numbers pass, and starts at 1 when x=0 (because there's a zero in the number zero). That was the first thing I did, and it's what I used to start out.

Next thing I realized was that right at 100, it switches to a y=x-k sort of formula, where k is a defined constant I don't want to solve for right now. So I made a formula that does y=x from x:(0,9). Well mod(x,100) does that, but it goes past x=9, so I took a minimum. That's where the min(mod(x,b^2),b-1) came from. b here was just 10, obviously.

The next thing I did was the part stuck at the end, the min(1,max...) part. It's just a function that fixes whatever problems come up due to the fact that 1 doesn't have a 0 in it, but 101 does. It's essentially an if statement that is 0 for x<=100, and 1 for x>100, assuming x is an integer.

That last part, the +(b-1)(floor.... part took absolutely forever to think of. I needed a way to make it so the min(mod...) thing would continue to step up, rather than go back to 0 at each 100 mark.

That's why it looks like an absolute mess, it's because the only way I could think of it was in steps.

>>57164337
>think about how to solve a problem hard enough till you come up with something.
Why does this make me chuckle?

>>57158170
Char=0
Count++

>>57164370
>>57164314
Oh right, my bad.
it will be For every ten thousands numbers, 0 will appear on 4 different places, 1000 times each.
The code is correct though.

>>57161815
here you go
```
z = ""
for i in range(100, 201):
z += str(i)

print(z.count('0'))
```

>>57164314
>1) number of zeros from 1-9999 - We can notice 0 appear on first from right place 999 times, on second 99 times, etc.
>on second 99 times
[note that he's counting from the right, i.e. 5678 first digit would be 8, whereas i will count from left, last digit would be 8]
no, there are 99 numbers 100,200,300....9900 but the last digit can be any, rather than 0 as in the above numbers, meaning there are 10x as many numbers as that which have 0 as the second digit, for a total of 990. Similiarly there are 900 numbers with 0 as their second digit.

>>57164438
There's a problem though: f(100,10)-f(99,10)=1 with your formula, which isn't right.

>>57158170

nigger a b = length . filter (=='0') $ concatMap show [a..b]

stdout

> nigger 100 200
22
it :: Int
(0.01 secs, 115,920 bytes)

how about

puts (100..200).to_a.to_s.split('').map{|x| x == '0' ? 1 : 0}.inject(:+)

>>57164015
Okay, I realized it doesn't work past 1000.

Also this >>57164591 is true. I've already wasted an hour on that equation, so I'm not really planning on fixing it all. If you want to fix it, you're going to have to modify part of that equation using logs, and then add on a final part that adds 1 each time it gets to a k1 * 10^k2 number, with k1 and k2 being integers.

>>57159704
fucking c faggots talk about readability and language being superios and this shit happens

>>57164702
it's code golf m8, i. e. how small of a program (source code) can you make that still solves the problem. so you remove whitespace etc. and do all other kinds of tricks to shorten your code at the expense of readability.

>>57164551
Oh shit you are right. I didn't noticed it because I tested first stage on numbers less than 1000.

fn stage1(d: i32, p: i32) -> i32 {
    let mut ret = 0;
    let mut n = d / 10;
    for i in 1..p {
        ret += (d / n - 1) * (n / 10);
        n /= 10;
    }
    ret
}

fn stage2(n: i32, d: i32, p: i32) -> i32 {
    (n / d - 1) * p * (d / 10)
}

fn stage3(mut n: i32, mut d: i32, p: i32) -> i32 {
    let mut ret = 0;
    n %= d;
    for i in 0..p {
        d /= 10;
        ret += (n / d + 9) / 10 * d;
        if (n / d) % 10 == 0 {
            ret += n % (d * 10) + 1;
        }
    }
    ret
}

fn zeros(mut n: i32) -> i32 {
    let mut d = 1;
    let mut p = 0;
    while d * 10 <= n {
        d *= 10;
        p += 1;
    }
    //println!("{}: {} {} {}", n, stage1(d, p), stage2(n, d, p), stage3(n, d, p));
    stage1(d, p) + stage2(n, d, p) + stage3(n, d, p) + 1
}

fn main() {
    let a = 100;
    let b = 202;
    
    for i in 99..101 {
        println!("{}: {}", i, zeros(i));
        //zeros(i);
    }
    
    println!("{}", zeros(b) - zeros(a - 1));
}

Let's say I have number 30456
First I divide this problem into 3 smaller problems:
1) number of zeros from 1-9999 - We can notice 0 appear on first from right 999 times, on second 990, on third 900, etc.
2) number of zeros between 10000-29999 - For every ten thousands numbers, 0 will appear on 4 different places, 40 times each
3) number of zeros from 30000-30456 - Is a little harder.
Let's forget about ten thousand part, and focus on 0456.
0 on 4th place will appear 457 times.
0 on 3rd place will appear only in 0000 to 0099 = 100 times,
0 on 2nd place will appear in packs of 10 every 100 numbers: 0000-0009, 0100-0109, etc. = 40 times
0 on 1st place will appear every 10 numbers: 0000, 0010, 0020, etc. = 45 times

And at the end we add 1 because 0 itself is a magic number that has leading zeros.

File: 1475886519526.jpg (121KB, 528x592px) Image search: [Google]

121KB, 528x592px

>>57158170

#include <iostream>

int main() {
    int nstart;
    int nend;
    int zero;

    nstart=100;
    nend=200;
    zero=0;

    for (int i=nstart; i<=nend; i++){

        for (int j=0; j <= i; j=j+10) {
            if(i == j){
                zero++;//dez em dez
            }
        }
        for (int k=100; k <= i; k=k+100) {
            if(i == k){
                zero++;//cem em cem
            }
            for (int q=1; q <= 9; q++) {
                if(i == k+q){
                    zero++;//x01 a x09
                }
            }
        }

    }
    std::cout << nstart << " -> " << nend ;
    std::cout << std::endl << "Total= " << zero ;
    return 0;
}

100 -> 200
Total= 22

took sometime but it works, should done with arrays its more easy.

>>57164917
could you test for 1,000,023 to 1,303,633
I'll have results with the simple O(n) method for verification soon.

>>57165306
let a = 1000023;
let b = 1303633;
Result: 255663

>>57163323
I'm pretty sure you never bothered reading the thread. Several solutions don't use strings

>>57165472
if you were thinking of the modulo 10 /= 10 solutions:
do you really think that a % 10; a /= 10 is significantly faster? what do you think casting an int to string does?
if there were better general solutions at the time of my post could you link them to me? i must have missed them.

>>57158188
Thank you for your honesty.

This is one of the most interesting yet clusterfucked threads on /g/.

>>57164917
Gotta admit, that's pretty cool. Props for winning the thread, anon. Also nice that you use rust and somehow manage to not have horrifyingly ugly code

>>57165802
Clearly you are the one who doesn't know an important part of "casting" (it's not casting) an int to a string: allocating memory.

Either way, it's irrelevant now that some dude has posted the right way after 10 hours

>>57158596
my daughter chino is so cute

using System;
using System.Linq;

public class Test
{
    public static void Main()
    {
        int num1, num2;
        while(true)
        {
            Console.WriteLine("Enter first number: ");
            string numS1 = Console.ReadLine();
            if(int.TryParse(numS1, out num1))
                break;
        }
        while(true)
        {
            Console.WriteLine("Enter second number: ");
            string numS2 = Console.ReadLine();
            if(int.TryParse(numS2, out num2))
                break;
        }
        int sum = 0;
        for(int i = num1; i <= num2; i++)
        {
            sum += i.ToString().Count(x => x == '0');
        }
        Console.WriteLine(sum);
    }
}

;^)

File: 1386460907430.jpg (117KB, 1058x705px) Image search: [Google]

117KB, 1058x705px

Ok now I feel dump as fuck for wasting so much time doing it hard way. I come up with better solution.

The nicest solution in O(log10(n)):

fn zeros(n: i32) -> i32 {
    let mut ret = 0;
    let mut d = 1;
    while d * 10 <= n {
        ret += (n - d) / (d * 10) * d;
        if (n / d) % 10 == 0 {
            ret += n % (d * 10) + 1;
        }
        d *= 10;
    }
    ret + 1
}

fn main() {
    let a = 100;
    let b = 200;
    
    println!("{}", zeros(b) - zeros(a - 1));
}

I hope it works properly. It gives the same results as >>57165384

>>57158170

(defun count-0 (max &key (min 0))
   (reduce #'+ (loop for i from min to max collecting (count #\0 (write-to-string i)))))

(count-0 200 :min 100) ; 22

>>57166461

(defn count-0 [max & {min :min :or {min 0}}]
    (reduce + (map #(count (re-seq #"0" (str %))) (range min (inc max)))))

>>57164647

nigger = length . filter (=='0') . concatMap show . enumFromTo

>>57166284
>uses fp lang
>solution isn't one liner
rethink your life, tee bee eich

>>57167233
>fp lang
What does it even mean?

>>57167233
>rust
>FP
To be honest, I don't blame you for getting confused because rust's syntax is an abomination.

>>57167258
nevermind, I thot that was ocaml because of the let's everywhere
move along plebeian

>>57167258
functional programming

>>57166284
Pretty nice. Now do what >>57160730 did and make it as compact as possible to finish it off.

>>57166615
which lisp?

Stupid niggers ITT.

How to find out how many 0's in x:

jews = 0
while (x >= 10)
if x % 10 == 10, then jews++
x /= 10

return jews

>>57167412
>calling people stupid
>doesn't know code tags
god damn

>>57167412
*10 == 0

>>57158170

λ sum [ 1 | d <- [100..200], '0' <- show d ]
22

>>57167412
O(n*log(n)) pleb

>>57159767
Tepru on rizon
She's a bitch and this is her only good picture

I have a partial O(log n) solution for numbers that don't contain any ‘0’s: e.g. 192839 which has 86763 zeroes. You can calculate this as 19283 + 19280 + 19200 + 19000 + 10000

Don't know what to change to make it work for numbers with 0s in them (i.e. ones that ‘stop’ in the middle of a string)

>>57167441
>'0' <- show d
what the fuck, what does this mean

>>57161113
lmaooooooo

>>57167626
If there is 0 in number you need to do something like this:
190832 has 85997 zeroes = 19083 + 19080 + 19000 + (19000 - 1000 + (190832 mod 1000) + 1) + 10000
See >>57166284 for solution.

>>57167699
pattern matches that fail inside a list comprehension desugar to the empty list

>>57158170

def numzeros(n):
    if n <= 0
        return 0
    return (n % 10 == 0) + numzeros(n / 10)

this'll tell you how many zeros in a number. You should be able to figure out the number in a range by using it

>>57167938
Makes sense. Couldn't be bothered working out the exact error term, thanks for doing it for me.

>>57158563

dontStab <- function(x, y){
  Ans <- 0
  for(i in x:y){
    Num <- strsplit(as.character(i), split = "")[[1]]
    Ans <- Ans + length(Num[Num == "0"])
  }
  Ans
}

>>57158322
we don't give a shit if OP is asking for homework or not. If we are interested in solving the problem we will, if not we won't.

>>57167970
C one line function

int nzer(int n) {
    return (n % 10 == 0) + (n > 10) ? nzer(n / 10) : 0;
}

>>57158170
Took me all of 8 minutes to write.

#include <stdio.h>

int countzeroes(int n)
{
    int zeroes = 0;
    while(n) {
        if(n % 10 == 0) zeroes++;
        n = n / 10;
    }
    return zeroes;
}

int main(void) {
    
    int start, finish, counter, total = 0;
    
    input:
    printf("Please specify a range of integers...\n");
    printf("START: "); scanf("%d", &start);
    printf("FINISH: "); scanf("%d", &finish);
    
    if(start > finish) {printf("Invalid range!\n");goto input;}
    
    for(counter = start; counter <= finish; counter++) {
        total += countzeroes(counter);
    }
    
    printf("There are %d zeroes in this range.\n", total);
    return 0;
}

>>57167454
nlog(n) is excellent. What is the better solution?

>>57160227
Nice unreadable one liner. A TA would punch you in the face for submitting turd like this.

You did it in pieces in your head, so save them as fucking variables

>>57161224
I see why you would give up on programming.

>>57160227
>pow

Just use ** you double nigger.

File: IMG_20161021_171136.jpg (38KB, 720x221px) Image search: [Google]

38KB, 720x221px

>>57167563

>>57169663
log(n)?

>>57163157
>using

Integer

>instead of
int

File: IMG_20161021_120855.jpg (53KB, 540x960px) Image search: [Google]

53KB, 540x960px

>>57158170
this is her now, feel old yet?

>>57167200

<interactive>:4:5:
    Non type-variable argument in the constraint: Foldable ((->) a)
    (Use FlexibleContexts to permit this)
    When checking that ‘nigger’ has the inferred type
      nigger :: forall a. (Enum a, Show a, Foldable ((->) a)) => a -> Int

>>57171713
Where did you get this pic from. Kek didn't realized she was balding.

No strings attached edition

#include <iostream>

using namespace std;

int zeros_in_nr(int nr) {
    int zeros = 0;
    do {
        if(nr % 10 == 0) zeros++;
        nr /= 10;
    } while(nr != 0);
    return zeros;
}

int zeros_in_range(int start, int end) {
    int zeros = 0;
    for(int i=start; i<=end; i++) {
        zeros += zeros_in_nr(i);
    }
    return zeros;
}

int main()
{
   cout << zeros_in_range(100, 200) << endl; 
   
   return 0;
}

>>57172085
maybe her Facebook, maybe one of the chats she attentionwhores in, can't remember

File: IMG_20161021_134701.jpg (90KB, 720x1280px) Image search: [Google]

90KB, 720x1280px

>>57172085

File: IMG_20161021_134810.jpg (117KB, 720x1280px) Image search: [Google]

117KB, 720x1280px

>>57172085
>>57172085

>>57172336
I lurked her (one of her?) Facebook but didn't saw much. I am not on her friend list tho.

>>57172367
>>57172391
I didn't saw these ones before. I guess I should look for the old edgy lainchan teen cool kids club. Is the gentoomen vola still a thing?

>>57172367
>>57172391
More forehead

>>57167332
Clojure

>>57172579
idk it's not from vola, it's from telegram

>>57172845
I'm not in the telegram shitposting group. Is it worth it?

>>57173034
not really, she's not really active on it anymore, and they won't let you in anyway because the admins are autistically against new people

>>57173063
Gonna stay on irc then. Not in the same channels cause I can only see this much of kpop and drama shitposting.

>>57173180
she's in the r/kpop discord too

>>57173210
What's the deal with kpop actually?

>>57173229
what do you mean

File: 1446638324755.jpg (53KB, 800x676px) Image search: [Google]

53KB, 800x676px

Am I on Twitter or something?

>>57173236
Several of the "lainchan" / "ricers" seemed to have taken an interest on kpop 2 years ago or so. For a while I thought it was ironic or a forced memesque inside joke but it stoke.

>>57173271
its a catchy music genre that keeps innovating, nothing wrong with it except the fact kpop idols make barely any money from it

>>57173271
Are you surprised that mentally fragile people are like to be targets of advertising masters and prone to actually fall for it?

The "popularity" of Korean Pop(ular) music in the West is the result of a successful campaign by the Korean government.

>>57173305
t. I've listened to psy and big bang's fantastic so I know everything about kpop

>>57158170

echo {100..200} | grep '0' -o | grep '0' -c

Lol, bash.

>>57173314
What are you trying to say with that meme and those implications?

ITT: ye olde challenge people's pride to make'em do your will

ayyyy lmao

>>57173289
>>57173305
I must be too old to follow trends anymore

I like too keep track of what the edgy band is up to though.

>>57173333
I'm saying you haven't actually listened to enough kpop to judge it, otherwise you wouldn't put its success down to marketing

>>57173346
Are you camille?

>>57173374
no who's camille

>>57173393
Some dude i know browses /g/ who sound like you and expected to spook.

>>57173334
he didn't do, he merely asked for a program

File: 1446071235973.png (798KB, 1183x887px) Image search: [Google]

798KB, 1183x887px

>>57173346
I have yet to hear Korean popular artist making albums critically acclaimed by critics
Electropop, Synthpop, Indie Pop, Psychedelic Pop, anything pop relate.

Please name a Korean artist whose talent has been recognised by critics like they did for The Knife, Depeche Mode, Tame Impala, Taylor Swift etc

It also seems you're dismissing the millions of dollars spent by the Korea Tourism Organization.

Japanese Pop music had at least some novelty and some originality in it when it spread in the West.


tl;dr kpop is fucking trash fuck off

>>57173455
why does he have a female name

>>57173537
literally f(x)

>>57173559
I don't know. Netherlands have strange traditions I guess.

>>57173584
I'm from there and I've never heard that, it's prob just an Internet name

File: ok frog.jpg (90KB, 960x960px) Image search: [Google]

90KB, 960x960px

>>57173332
Good one

>>57173597
Pretty sure it's his real name (there are international students that are dude named Camille in my uni, though not from Netherlands). But anyway, my spooking attempt failed.

>>57173210
She says she's a student. Did she felt for the cs meme?
I assumed she was neet with autismbux given she's legit crazy by mental health standard

>>57173986
she didn't even finish high school lmao, she's been in the mental ward several times

>>57158170
in a pseudo-code I would follow this:

>create input fields for both integers
>Have program pull both integers.
>create a for loop based on those integers to go through each and every number.
>during each rotation, separate every number in each integer to become an array.
>count each 0 in that number and put it into a separate variable.
output the separate variable.

>>57173480
>he didn't do, he merely asked for a program
Knowing that at the slightest suggestion, many will begin a e-peen showoff shitfest.

If you know well the crowd you are asking, you dont even have to ask explicitly.

/g/ may not be your helpdesk, but surely is your programming pajeet just one post away

>>57174334
Yeah, that's why I was surprised to her about her being an "engineering students" and echoes of her bitching about tests she didn't studied for. Last year or so, she was interned coz she tried to stab herself with a ballpen or something.

>>57174581
it's an interesting challenge you know? simple problems like that are fairly common, and for some enjoyable to solve. The majority of posts aren't e-peen showoffs, there isn't even a name, upvotes or anything you could achieve by posting a good solution, nevermind that most solutions aren't that good. People just enjoy doing small programming exercises occasionally.

>>57174652
damn didn't know she tried to stab herself, I only remember her being interned and getting fingered by another crazy guy

for those discussing complexity:

pretty sure this is O(n*log(n))

>>57174703
She stabbed herself with a pen and went to brag about it on irc (#plez and #dprk if I remember) then was interned. There used to be pictures of the ambulance car and weird posts about strange kids in the facility on her older (now deleted ?) Twitter.

What's/ when's the story about the crazy guy finger? Didn't know about it.

at least, for the naive implementation

>>57174784
that's from when she was in the crazy ward, she ended up dating him and drinking bleach with him tho

very strictly speaking, it will never be below O(n), since you have to look at the entire length of the input to find the answer, but it all depends on the model you use

>>57158240
If number%10==0 is true you know the last digit is 0.
If (number/10)%10==0 you know the second digit is 0
Generally
If (number/(1*pow(10,n)))%10==0 you know the n'th digit starting at 1 with single digit numbers is 0.

Should be enough to figure it out.

>>57174858
>last digit
Sorry I'm confusing. I meant the first digit.

>>57174810
I didn't know she was this much stupid.
How old is she actually? Isn't she still on her /white/ bedroom?

>>57174940
she moved in with a 30-something woman

the question to ask is: are you measuring complexity with respect to the interval, or the length of the input? the input length is already compressed, and you don't have to enumerate the interval itself to solve this, since the number of zeros for a given order of magnitude is simple to calculate.

>>57158170

for i in {100..200} ; do echo $i | grep 0 | awk -F0 '{print NF-1}' ; done | awk '{s+=$1} END {printf "%.0f", s}'

>>57175010
What? I though she was 25 or so.
So she roommates with someone "much" older... I wouldn't have expected.

>>57158861
probably Arduino's library, I think I've used it as well

>>57158913
no u

>>57158264
>>57158285
>>57158913
>>57159522
>>57166102
>using the smiley with a carat nose

>>57174768
>>57174788
>>57174832
m8, I solved it in log(n).
>>57166284

>>57175011
There is no length of input, a and b are just numbers, not strings.
The minimal complexity in looking for all zeros from 0 to n in base b is O(logb(n)). There might be more optimal solutions for looking at zeros between a and b where a and b are natural numbers though.

>>57175171
anything to get away from her parents

>>57158170
Seems like that'd be more of a mathematician's domain to come up with the algorithm, a programmer would just be in charge of implementing it in code.

>>57167563
it's actually TopKuk on Rizon

>>57175327
>There is no length of input, a and b are just numbers, not strings
Fundamental misunderstanding of formal computer science detected. A lot of people do make this mistake, even those who have degrees in it. (which goes to show how un-academic computer "science" really is, but that's another rant)

Runtime complexity is ALWAYS based on length-of-input in theoretical CS. And numbers DO have length, too. A number must be represented as a series of bits or basically any non-unary sequence of digits. Therefore, the number's value (which is what you are talking about) is *exponentially* proportional to input length. Your algorithm is O(log(n)) if n is the number's value, but is only O(n) if n is the number's length. In real life, that's basically never a problem, because you can still handle huge numbers easily. Check out pseudo-polynomial time (https://en.wikipedia.org/wiki/Pseudo-polynomial_time) for a very similar class of problems which are technically exponential, but in practice are almost always solved quickly.

>tfw you figure out how to do it in O(1)

>>57175946
>everything is O(1) because you have limited memory size :^^^^^)

>>57176017
what did he mean by this? are you trying to sell me RAM you filthy merchant

>>57176017
finally someone who understands the important details of theoretical CS

Still technically incorrect, though, because a large class of turing machines will never halt. (inb4 you have limited energy to run the machine)

>>57176051
theoretical machines theoretically have infinite energy so this is not a big problem

>>57176031
In CS theory, any problem with a finite number of possible inputs is doable in constant time. Imagine a look-up table that is indexed by the entire contents of your computer's memory, and each entry is the answer to the problem given what the contents of your memory are. As long as memory is finite, such a table is possible to build and can solve any problem with a single, O(1) lookup.

>>57176085
interesting. not much of a theory fan myself. do engineering so LUTs and why they are so based is familiar to me, but only through practical use.

>>57175914
I understand what you mean.
However I think parsing input is not part of this algorithm, I assume the data is present in memory at the beginning of the algorithm. For example: algorithm that checks if number is even or odd would be O(1) because it only has to check the least significant bit of data. I've never really seen anyone considering parsing input as part of algorithm.
Also of course by n I mean the value. Again I've never seen anyone using length of representation of value in some base instead of value itself.
But according to the wiki it actually is a thing. Well, I'm just undergrad, we barely get definition of these notations.

>>57158170
You're all bad at optimizing your code and you failed math class.

To add to the shame, I'm going to submit my solution in JS. In v8, it's probably faster than most of the terrible C solutions here, kek. Some of you fucks don't even realize that some numbers containing zero aren't multiples of ten, or think that converting to a damn string is somehow not the worst possible option on the planet.

function numberOfZeros(low, high) {
    var zeros = 0;
    for (var i = low; i <= high; i++) {
        var maxExp = Math.floor( Math.log10( i )); // floor of log10 of i gives us the exponent needed to make it a single digit.
        for (var j = 0; j < maxExp; j++) // Iterate through every exponent.
            if (Math.floor(i/10**j) % 10 == 0) zeros++; 
    }
    return zeros;
}

// Test case
console.log( numberOfZeros(100, 200) == 22 );

// Bench mark
(function() {
    const preTime = performance.now();
    for (var penisesRapingChildren = 0; penisesRapingChildren < 9000; penisesRapingChildren++) numberOfZeros();
    const postTime = performance.now();
    console.log(postTime - preTime);
    // Looks like 9000 iterations of my function with OP's (100,200) test case completes in less than a fucking millisecond on 2gb of RAM and an ARM processor in Chrome.
})();

Hypothetically, I could replace this with just function f(){return Infinity;} and have a technically correct answer.

>>57158264
>he thinks his one liner isn't worse than an incorrect solution
At least testcases could catch why his code is broken.

>>57158356
Still waiting on you to redeem yourself. That isn't even a function, and is absolutely horrific logic.

>>57176085
>>57176127
The point I was trying to make (>>57176017) is that big-O notation is useless without context. O(X) describes a class of functions. But what that function measures depends entirely on the context.

For example, this statement makes sense: “This algorithm requires O(n^2) integer additions where n is the number of digits in the input”
This statement does not, inherently, make sense: “This algorithm is O(n)”. Without context, such statements are meaningless.

>>57176264
Wrong.

>>57176259
>wants to get on a moral mathfag high horse
>still presents a dogshit babby-tier unoptimized brute force algorithm
>thinks his stupid floating point division algorithm and imprecise math is going to be faster than converting to a string

not sure if bait but if bait then you seriously got me hard

>>57176259
>// Looks like 9000 iterations of my function with OP's (100,200) test case completes in less than a fucking millisecond on 2gb of RAM and an ARM processor in Chrome.
Cute, now do it for the range 1 million to 1 billion

>>57176199
Yeah, I myself didn't encounter the "input length" thing until grad school, but it's an interesting and very important distinction in theory.

For example, there are problems that, for all practical purposes, are solvable in linear time with respect to the value of the number, but if you could make a linear-time solution with respect to the length of the number, you get to claim your million dollars because you proved that P equals NP. (I'm thinking of the knapsack problem https://en.wikipedia.org/wiki/Knapsack_problem, and plenty of related problems.)

Anyway, back to the topic: even if you assume that the number is already all in memory, the

d * 10 <= n

operation you performed is still linear: it needs to check every bit in n to do the comparison. It may seem like splitting hairs in this problem, but, like I said above, it's definitely important in other contexts.

>>57174858
>If (number/10)%10==0 you know the second digit is 0
101 / 10 == 10.1
10.1 % 10 == 0.1

Looks like you failed math. Get off /g/ and onto a board where you belong, like /pol/.

>>57176199
>However I think parsing input is not part of this algorithm, I assume the data is present in memory at the beginning of the algorithm. For example: algorithm that checks if number is even or odd would be O(1) because it only has to check the least significant bit of data. I've never really seen anyone considering parsing input as part of algorithm.
At the deepest, most basic theoretical framework, the underlying assumption is generally that you're counting the number of execution steps in a turing machine that's started on an input tape which contains the entire input

In the context of that rigorous framework, if you need to process the entire input then you need to spend at least O(length) steps.

>>57176332
>modulo on integers gives a float
>modulo on floats works at all
Get off /g/ and onto a board where you belong, like /pol/.

>>57176284
almost useless at least
he never said if n is the number itself or the digits of the number, which is a big difference

>>57176199
>>57176313 here again

I actually thought of a more relevant example: determining if a number is prime. For a long time, it took O(sqrt(n)) if n is the *value* you wish to determine is prime. Of course, since we want huge primes for crypto stuff, this does become slightly untenable, because for every bit you want to add to n, the value of n can *double*, which will even overpower the square root and make the overall algorithm still be exponential. It wasn't until the early 2000s that people came up with deterministic algorithm for checking if a number is prime that was non-exponential with respect to length.

>>57176391
*division

>>57176313
>the d * 10 <= n operation you performed is still linear: it needs to check every bit in n to do the comparison.
if you view the program as an abstract description of an algorithm, sure. But if you view it as it is(input is limited to x bits etc.) then that comparison is O(1) as it's done in hardware, for all digits simultaneously.

>>57176313
>For example, there are problems that, for all practical purposes, are solvable in linear time with respect to the value of the number, but if you could make a linear-time solution with respect to the length of the number, you get to claim your million dollars because you proved that P equals NP. (I'm thinking of the knapsack problem https://en.wikipedia.org/wiki/Knapsack_problem, and plenty of related problems.)
Sorting is also solvable in linear time with respect to the value range of the numbers you're sorting, for example.

There are more startling examples where it matters what exactly you're measuring; for example factorization by naive trial division is O(n) with respect to the value of the number, but O(2^n) with respect to the number of bits. Cases like this is why you usually have to use the number of bits in the input as your basis for ‘n’, rather than the arithmetic value that they denote. So for the purposes of this algorithm, the “optimal” solution would be O(n) w.r.t the number of bits in the input (which is O(log10 n) w.r.t the value of the input).

There's some other algorithm that I'm trying to think of which is polynomial in the number of fixed-size integer operations that you have to perform, but is still an NP-hard problem - because to solve it for unbounded sizes is also exponential in the number of bits, since you need larger and larger operations.

In general, be very careful about what exactly you're measuring with your ‘n’ and your function. If in doubt, specify it.