CODEWITHSUNDEEP
javaregex
CarlJohn
CarlJohn

Reputation: 727

Count zeros in the series of N numbers - Java

i want to count the number of zeros in a N-range of numbers starting from 0.

If the N is 100 means,then the range should starts from 0 to 100 then and the count should be 12.

Below code works till some 10^6

private static int calcZeros(String input){
        int count = 0;

        int n = Integer.parseInt(input);
        for(int i = 0;i<=n;i++){
            count += String.valueOf(i).replaceAll("[a-zA-Z_1-9]","").trim().length(); 
        }
        return count;
    }

If the N exceeds 10^6, it hangs,Obiviously, for loop runs for long duration.

My Question here is ,this is right approach to find the zeros count?

Suggest me some fastest way to do the count.

Upvotes: 0

Views: 1789

Answers (4)

akbarian
akbarian

Reputation: 51

try this

int n = 1000000;
int count  = 0 ;
Pattern pattern = Pattern.compile("0+");

for(int i = 0; i <= n ; i++ ) {
    Matcher m = pattern.matcher(String.valueOf(i));
    while (m.find()) {
        count += m.group().length();
    }
}
System.out.println(count);

Upvotes: 0

jseteny
jseteny

Reputation: 420

This algorithm calculates the number of zeros until 1000000000 in 20 seconds. I hope it helps.

int count = 0;
int n = 1000000000;
for (int i = 0; i <= n; i++) {
    int m= i;
    do {
        if (m % 10 == 0)
            ++count;

        m = m / 10;
    } while (m > 0);
}
System.out.println("count = " + count);

Upvotes: 0

libik
libik

Reputation: 23029

This is (semi)combinatoric problem.

For example imagine 4-digit number :

We start to find all numbers with one zero.

At first position (from left to right), you can use numbers from 1-9, then 1-9, then 1-9 and then there will be 0, so there is no other option.

its 9*9*9 possibilities.

And that zero can be in three positions.

Then we have to find all 4-digit numbers with two zeroes.

We can use Binomial coefficient where (n k) in our case will be : n=number of digits - 1, k = number of zeroes and then you multiply it by 9*9, because thats all possibilities of other numbers.

I have to go now, so I cant finish it for any possible number, but for given number of digits, this shold be working :

public static void main(String[] args) {
    System.out.println(numberZeroes(2));
}

public static int numberZeroes(int digits) {
    int result = 0;
    for (int i = 1; i <= digits - 1; i++) {
        result += binomial(digits - 1, i) * Math.pow(9, digits - i);                        
    }

    return result+1;
}

public static int binomial(final int N, final int K) {
    BigInteger ret = BigInteger.ONE;
    for (int k = 0; k < K; k++) {
        ret = ret.multiply(BigInteger.valueOf(N - k))
                .divide(BigInteger.valueOf(k + 1));
    }
    return ret.intValue();
}

Upvotes: 1

assylias
assylias

Reputation: 328598

Instead of using strings and regex, it would be a lot faster to keep dividing by 10 - for example:

int i = 96;
int firstDigit = i / 10;
int secondDigit = i - firstDigit * 10;

For arbitrarily large numbers, you just need to replace that by a while loop.

Upvotes: 0

Related Questions