Problem 10783 at the UVa Online Judge, also known as *Odd Sum*, asks us to compute the sum of odd numbers in a given range. The problem is easy, but fun, and can be solved in a similar way to the first Project Euler problem.

## Interpretation

We are given two integers and , where . Our job is to compute the sum of the odd numbers between and , inclusive. The bounds are so small that almost any solution will be fast enough. We can simply loop from to and sum up all odd numbers we find. Perhaps we will start with that, and then try to improve it as we go?

## Implementation

Let’s first create the *main* method. It’s very simple, and should look something like:

public static void main(String[] args) throws Exception { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out, true); // read the number of test cases int tests = in.nextInt(); // loop through each test case for (int t = 1; t <= tests; t++) { // read a and b for the current test case int a = in.nextInt(), b = in.nextInt(); // print the result appropriately out.printf("Case %d: %d\n", t, OddSum3(a, b)); } }

The *OddSum* method can then be implemented with a simple *for*-loop like described above. To check if a number is odd, we simply check if there is any remainder when the number is divided by , which can be done using the modulus operator.

public static int OddSum(int a, int b) { int sum = 0; // go through each number from a to b for (int i = a; i <= b; i++) { // if the current number is odd if (i % 2 != 0) { // add it to the running sum sum += i; } } return sum; }

The current solution is fast enough to get accepted, but we are having way too much fun to stop here.

Our *OddSum* method is very wasteful. Half of the numbers it checks aren’t odd. We can easily fix that by noting that if an integer is odd, then is the next odd integer. With this in mind we can start at the smallest odd integer greater than or equal to , and loop through each odd number until we reach . And by the way, the smallest odd integer greater than or equal to is if is odd, and if is even.

public static int OddSum(int a, int b) { // if a is even if (a % 2 == 0) { // then the smallest odd integer we want is one greater than a a++; } int sum = 0; // go through every odd number from a to b for (int i = a; i <= b; i += 2) { // and add it to the running sum sum += i; } return sum; }

This method is better than the last one, but we can still do better. That *for*-loop is annoying us. We would much rather have a single closed-form expression.

Let denote the smallest odd integer greater than or equal to , and let denote the largest odd integer less than or equal to .

Then we can express this problem as an arithmetic series. Basically we are looking at the n-term arithmetic series where

One important thing however, is to figure out what , which we can do since we know what is:

We are trying to find the sum of the terms up to and including , which means that we need to sum up the first terms in the sequence. The sum of the first terms in our sequence:

Combining these formulas into our *OddSum* method gives us:

public static int OddSum(int a, int b) { // if a is even if (a % 2 == 0) { // then the smallest odd integer we want is one greater than a a++; } // if b is even if (b % 2 == 0) { // then the largest odd integer we want is one less than b b--; } // find the index of b in the sequence int i = (b - a + 2) / 2; // calculate the sum of the first i numbers in the sequence return i * (a + (a + 2 * (i - 1))) / 2; }

Look at that! No ugly *for*-loops.

## Conclusion

Today’s problem was easy, but fun. We started off by creating a straight-forward solution which unfortunately worked due to small test cases. We did one minor optimization and then finally finished with a neat closed-form solution.

The blog image graphically shows why the sum of the first odd numbers is . We could also have solved this problem using that formula and the inclusion-exclusion principle, but I’ll leave that as an exercise.

You can take a look at the complete source code here.

So how would/did you solve this problem? Leave a comment and let us know.

Nice 😀

Only two lines:

const int n=(end-start)>>1;

result=start*(n+1) + n*(n+1);