Sum of First N Even Numbers Divisible by 3 in Java | Baeldung

1. Overview

In this tutorial, we’ll explore calculating the sum of the first N even numbers divisible by 3 using Java. This can be solved using different approaches.

We’ll examine two distinct methods to illustrate these approaches. The first method is the brute force method. This method involves a step-by-step approach where we discuss each even number and determine its divisibility by 3. While simple to understand, it may not be the most efficient for large values of N. The second method we’ll discuss is the optimized mathematical approach. This method leverages the inherent properties of even numbers divisible by 3 to derive a formula for direct calculation. This approach offers significant performance improvements, especially when dealing with large datasets of numbers.

2. Brute Force Method

The brute-force method involves iterating through numbers, identifying those that are even and divisible by 3, and adding them to a running total. This is a straightforward approach, but it may be inefficient because it checks every even number individually, rather than focusing directly on multiples of 6. Since any number divisible by 2 and 3 is also divisible by 6 (as 6 is the least common multiple of 2 and 3), focusing on multiples of 6 allows us to skip unnecessary checks for numbers that don’t meet both conditions.

2.1. Implementation with for Loop

For our code examples, we’ll define NUMBER as 7, which represents the first 7 even numbers, and EXPECTED_SUM as 18 (6 + 12), which is the expected result of this calculation:

static final int NUMBER = 7;
static final int EXPECTED_SUM = 18;

In the next example, we’ll use a for loop to achieve the result:

@Test
void givenN_whenUsingBruteForceForLoop_thenReturnsCorrectSum() {
    int sum = 0;

    for (int i = 2; i <= NUMBER * 2; i++) {
        if (i % 2 == 0 && i % 3 == 0) {
            sum += i;
        }
    }

    assertEquals(EXPECTED_SUM, sum);
}

Here, we check each even number starting from 2, and the loop continues until we’ve identified the first N numbers divisible by both 2 and 3. The time complexity is O(N) since we iterate until we find N numbers. In this case, we check many numbers that aren’t divisible by 2 and 3.

2.2. Functional Programming Approach

We can leverage Java’s functional programming features for a more modern approach. Using the Stream API, we can generate an infinite Stream of numbers, then filter this Stream to include only even numbers, limit it to the first N even numbers, and finally filter those that are divisible by 3 before summing them. This functional style can be more concise and declarative:

@Test
void givenN_whenUsingFunctionalApproach_thenReturnsCorrectSum() {
    int sum = IntStream.iterate(2, i -> i + 1)
      .filter(i -> i % 2 == 0)
      .limit(NUMBER)
      .filter(i -> i % 3 == 0)
      .sum();

    assertEquals(EXPECTED_SUM, sum);
}

This implementation uses IntStream.iterate() to generate an infinite Stream of Integers starting from 2. This approach isn’t only concise but also inherently parallelizable if necessary.

2.3. Improved Brute Force Method

The brute-force method can be further improved by observing that even numbers divisible by 3 are also divisible by 6. This means that instead of checking every even number, we can directly check numbers that are multiples of 6. This optimization reduces the number of checks we need to perform, making the method more efficient:

@Test
void givenN_whenUsingImprovedBruteForce_thenReturnsCorrectSum() {
    int sum = IntStream.iterate(6, i -> i + 6)
      .limit(NUMBER / 3)
      .sum();

    assertEquals(EXPECTED_SUM, sum);
}

By directly iterating through multiples of 6, we improve the performance of the brute-force method, making it more efficient without changing its core structure. This optimization makes the algorithm faster in practice, but the overall time complexity remains linear because the number of iterations is directly proportional to N.

3. Optimized Mathematical Approach

In the brute-force methods, we iterated through numbers and checked whether each was divisible by 6 to find even numbers divisible by 3. While effective, these approaches can be further optimized by leveraging the mathematical insight that the numbers we’re summing are multiples of 6. Therefore, instead of iterating through numbers and checking divisibility conditions, we can directly calculate the first N/3 multiples of 6 and sum them. This is because, out of every three even numbers, only one will be divisible by 3, so the first N even numbers divisible by 3 are the first N/3 multiples of 6.

3.1. Mathematical Insight

Every even number divisible by 3 is a multiple of 6.
Instead of iterating through numbers, we can directly calculate the first N multiples of 6 and sum them.
The first N multiples of 6 are 6 * 1, 6 * 2, 6 * 3, …, 6 * N. Therefore, we can calculate the sum as follows:
```
Sum = 6 * (1 + 2 + 3 + ⋯ + N)
```
The sum of the first N natural numbers is given by the formula:
```
(N * (N + 1)) / 2
```
Using this formula, the sum of the first N/3 multiples of 6 can be computed as:
```
Sum = 6 * (N / 3 * (N / 3 + 1)) / 2 = 3 * (N / 3) * (N / 3 + 1)
```

This approach avoids looping altogether, making it more efficient than brute-force methods, especially for large values of N.

3.2. Optimized Mathematical Code

We directly calculate the sum using the formula for the sum of the first N / 3 multiples of 6:

@Test
void givenN_whenUsingOptimizedMethod_thenReturnsCorrectSum() {
    int sum = 3 * (NUMBER / 3) * (NUMBER / 3 + 1);

    assertEquals(EXPECTED_SUM, sum);
}

This approach is much faster because it avoids looping altogether and reduces the problem to a simple arithmetic calculation. The time complexity of this approach is O(1), as it performs a constant number of operations, regardless of the value of N.

4. Comparing the Two Approaches

The brute-force methods and the optimized mathematical approach differ mainly in performance, simplicity, and flexibility.

In terms of time complexity, the brute-force methods have a complexity of O(N), as they require iterating over numbers. Even the improved brute-force method, while more efficient, still depends on looping. On the other hand, the optimized mathematical approach uses a direct formula, giving it a constant time complexity of O(1), making it significantly faster, especially for large N.

Regarding simplicity, the brute-force methods are straightforward but involve loops and conditions, making them slightly longer and more involved. The optimized method is much cleaner and more concise, as it directly applies a formula. However, it requires some familiarity with mathematical principles.

When it comes to flexibility, the brute-force methods are more adaptable. If the problem changes, like summing numbers divisible by a different number, these methods can easily be adjusted. The optimized approach, however, is specialized for multiples of 6 and would need a new formula for different conditions.

The following table provides a concise summary of the key differences:

Brute Force

Improved Brute Force

Optimized Mathematical

Time Complexity

O(N)

O(1)

Space Complexity

O(1)

Simplicity

Easy, loop-based

More efficient loop

Very concise, uses a formula

Flexibility

Adaptable to different conditions

Less adaptable, formula-specific

5. Conclusion

In this article, we explored two main approaches for calculating the sum of the first N even numbers divisible by 3: brute-force methods and an optimized mathematical approach. The brute-force approach, though adaptable, involves iterating through numbers with O(N) complexity. At the same time, the optimized method uses a direct formula with constant time, O(1), offering better efficiency but less flexibility.

As always, the source code is available over on GitHub.

Persistence

REST

Security