# Counting multiples of 3 up to a given number

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 108.

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 109.

• Can you think of a simple mathematical formula which computes the result directly, without the need for a loop? Commented Jul 20, 2019 at 16:58
• Is it dividing the given number by 3? Oh no Commented Jul 20, 2019 at 17:04
• It might be better to include the entire program if this is most of the program. We have a lot of space for code. Commented Jul 21, 2019 at 16:16
• Ignoring the closed-form solution of this particular problem, I would suggest you use IntStream.iterate(3, i -> i+3) Commented Jul 21, 2019 at 19:38
• @Evorlor Time limit error. Commented Jul 22, 2019 at 13:21

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++;
}

• you missed a trick here, appending count++ in the loop Commented Jul 20, 2019 at 17:41
• for(int i = 3; i <= x; i += 3, count++); Commented Jul 20, 2019 at 17:42
• @dfhwze That “trick” doesn’t make the code run any faster, and can lead to errors if you forget/don’t notice the trailing semicolon. I would call it out reviewing other people’s code here on Code Review. I certainly didn’t “miss” it, and highly recommend against it. When iterating over a non-trivial body, with two or more iterators, incrementing all of them in the increment portion of the for() statement is proper, and can improve readability of the code. Commented Jul 20, 2019 at 19:22
• That "trick" was a lightweight joke. Didn't mean to step on anyone's toes here. Commented Jul 20, 2019 at 19:25
• @dfhwze My compiler would refuse to compile it. It gives a warning when a semicolon immediately follows an if or for because it is most likely a bug, and any warning is turned into an error. Commented Jul 21, 2019 at 21:51

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)\$$.

• The title does state counting, not computing :p Commented Jul 20, 2019 at 17:28
• Yep, I figured. I'll keep the question up as a reminder to me that most simple problems will have simple solutions. Commented Jul 20, 2019 at 17:29
• @dfhwze That's only since someone butchered the title. It originally said finding. Commented Jul 20, 2019 at 23:07

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
$$$$

• Could you be specific about what is better? I'm guessing you mean the elapsed time, rather than (say) memory usage or energy consumed. Also, why this improves it is also worth mentioning (given that the parallelisation overhead is probably fairly high compared with the work). Commented Jul 24, 2019 at 13:58
• I was talking only about total time, it's true that I've not taken into account any other factor like memory or energy. Also, it's possible that results may vary according the computer. I'm sure there would be a way more clever and optimized solution (and I'll be glad to know it); however, in my opinion, simpler solutions are good enough in some cases. Commented Jul 24, 2019 at 15:06

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.

• I'm using Java here. Doing long/int division in Java ignores the decimal section anyways. But thanks for the answer, I'll keep it in mind for a later use. Commented Jul 21, 2019 at 4:51
• You know, in java 11, that actually compiles :P we have autotyping now Commented Jul 22, 2019 at 18:45
• I've been noticing Java lags behind on new features. Lambdas weren't introduced until Java 8 whilst they were a part of C# for much longer. Commented Jul 23, 2019 at 1:42
• Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. Commented Jul 24, 2019 at 16:21