Counting multiples of 3 up to a given number

Question

I'm attempting a practice problem in Codeforces that requires you to find the number of multiples of 3 less than or equal to a given number. I have written the following code but it gives a TLE once the test case reaches the order of 10⁸.

int x = Reader.nextInt();
int count = 0;

for(int i = 3; i<=x; i++){
    if(i%3 == 0){
        count++;
    }
}
System.out.println(count);

Is there any way I can further optimize this code? The test cases max out at 10⁹.

Answer 1

If you are insisting on counting, instead of computing the answer, you can optimize your counting loop by just looping over the multiples of 3:

for(int i = 3; i <= x; i += 3) {
    count++;
}

Answer 2

Use your brain, not brute force. How would you solve the problem if it were presented in a math test, and you couldn't use a computer?

Your solution requires \$O(x)\$ time; it should be possible in \$O(1)\$.

Answer 3

Using lambdas you can use multithread easily, it should improve your results:

IntStream.rangeClosed(3, x).parallel().filter(n -> n%3 == 0).count()

or, in case you need long values:

LongStream.rangeClosed(3L, x).parallel().filter(n -> n%3L == 0L).count()

---

I tested it with the following example:

public static void main(String[] args) {

        Instant start, end;
        long x = 24923869024L;
        long count = 0;

        // normal loop
        start = Instant.now();
        for (long n=3L; n<=x; n++) {
            if (n%3L==0L) count++;
        }
        end = Instant.now();
        System.out.println("method 1, result = "+count+", time = "+Duration.between(start, end));

        // non-parallel stream
        start = Instant.now();
        count = LongStream.rangeClosed(3L, x).filter(n -> n%3L == 0L).count();
        end = Instant.now();
        System.out.println("method 2, result = "+count+", time = "+Duration.between(start, end));

        // parallel stream
        start = Instant.now();
        count = LongStream.rangeClosed(3L, x).parallel().filter(n -> n%3L == 0L).count();
        end = Instant.now();
        System.out.println("method 3, result = "+count+", time = "+Duration.between(start, end));

    }

with the results:

method 1, result = 8307956341, time = PT33.55S
method 2, result = 8307956341, time = PT40.611S
method 3, result = 8307956341, time = PT12.637S
```

Answer 4

If I were to compute the answer, I'd do (language shown is C#):

var n = 1e8;
int v = n / 3;

6 has two multiples of three less than or equal to it: 6 / 3 == 2 127 has 42: 127 / 3 == 42.3333, thus Math.floor(127 / 3) == 42.

Likewise, 3 * n will have n multiples of three, including three itself.

---

Rather than having to iterate 1e8 - 2 times in a for-loop (similar amounts are often used for benchmarking tests), we just have to boil it down to a single integer division.