6
\$\begingroup\$

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.

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

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++;
}
\$\endgroup\$
  • \$\begingroup\$ you missed a trick here, appending count++ in the loop \$\endgroup\$ – dfhwze Jul 20 at 17:41
  • 2
    \$\begingroup\$ for(int i = 3; i <= x; i += 3, count++); \$\endgroup\$ – dfhwze Jul 20 at 17:42
  • 5
    \$\begingroup\$ @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. \$\endgroup\$ – AJNeufeld Jul 20 at 19:22
  • 1
    \$\begingroup\$ That "trick" was a lightweight joke. Didn't mean to step on anyone's toes here. \$\endgroup\$ – dfhwze Jul 20 at 19:25
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – gnasher729 Jul 21 at 21:51
11
\$\begingroup\$

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

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

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
```
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – Toby Speight Jul 24 at 13:58
  • \$\begingroup\$ 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. \$\endgroup\$ – Luis Iñesta Jul 24 at 15:06
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – therealshankman Jul 21 at 4:51
  • \$\begingroup\$ You're welcome. \$\endgroup\$ – VisualPlugin Rōblox Jul 22 at 7:23
  • 2
    \$\begingroup\$ You know, in java 11, that actually compiles :P we have autotyping now \$\endgroup\$ – mackycheese21 Jul 22 at 18:45
  • \$\begingroup\$ 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. \$\endgroup\$ – VisualPlugin Rōblox Jul 23 at 1:42
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Toby Speight Jul 24 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.