How to efficiently find if numbers in a given range contains either 1 or 3, but not both? I am having a trouble speeding up my implementation. The question is, given a range of numbers from long a to long b, find how many lucky numbers are between a and b inclusive. A number is a lucky number if it contains either 1 or 3. If it contains both 1 and 3, it is not a lucky number.

Currently, I am iterating over from a to b, inclusive, using for loop, and have a while loop in each iteration where a while loop continues until current number is > 0. In the while loop, I use modulo 10 to get the last digit, check if it's 1 or 3, then set the current number to the number/10.

Is there a way to make this more efficient for range from 10000000000 to 20000000000? With my implementation, it takes around 160 seconds.

Here is my code: 

public class Main {

    public static void main(String[] args) {

        long start = 10000000000L;
        long end = 20000000000L;

        int total = 0;

        double startTime = System.nanoTime();

        for (long i = start;i &lt;= end; i++) {
            int numOf1 = 0;
            int numOf3 = 0;
            long number = i;
            while (number &gt; 0) {
                long lastDigit = number % 10;
                if (lastDigit == 1) {
                    numOf1++;
                } else if (lastDigit == 3) {
                    numOf3++;
                }

                if (numOf1 &gt; 0 &amp;&amp; numOf3 &gt; 0) {
                    break;
                }
                number /= 10;
            }

            if (numOf1 &gt; 0 || numOf3 &gt; 0) {
                total++;
            }
        }

        System.out.println(total);
        double endTime = System.nanoTime();

        System.out.println((endTime - startTime) / 1000000000);


    }

}
A Bug


if (numOf1 &gt; 0 || numOf3 &gt; 0) {
    total++;
}



That overcounts. The definition of "lucky number" included "if it contains both 1 and 3, it is not a lucky number", but numbers that contain both a 1 and a 3 are counted. The break in the while-loop exits that loop when that condition is detected, but then the code above still runs. You could use:

if ((numOf1 &gt; 0) != (numOf3 &gt; 0)) {
    total++;
}


The != between two booleans is a slightly tricky way to say "one of them but not both". Of course that can be written out more explicitly.

An other bug


int total = 0;



Do you know how big the result is? By my count it's just over 3.48 billion. That's a problem, int only goes just over 2.14 billion. The count doesn't go over 4.29 billion, so you could still use int, and then interpret it as an unsigned integer later (eg printing total &amp; 0xFFFFFFFFL). But that's strange, a bit advanced, not for beginners. Using long total = 0; is a simpler and more sensible solution.


  Is there a way to make this more efficient for range from 10000000000 to 20000000000?


There are some specific properties of that range that you could use.

First, let's ignore 20000000000 itself, it contains neither a 1 nor a 3.

Then, every number in the range for sure has at least one 1 in it, so you don't need to test it, this is something you already know. That would let you simplify the test to "check if there is any 3 in the number".

Counting without brute force

Forgetting the leading 1, the numbers in our range have 10 "variable" digits.
How many 10-digit strings of digits 0..9 don't have a 3 in them? Every place has 9 possible digits left instead of 10, so rather than pow(10, 10) it will be pow(9, 10).

pow(9, 10) is something that you can calculate easily, even with just Math.pow(9, 10). It's normally not really proper to use doubles for integer calculations, but this one works.


  With my implementation, it takes around 160 seconds.


Does it actually? That's an order of magnitude faster than it runs on my PC.