# UVa 10783: Odd Sum

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 $a$ and $b$, where $0 \le a \le b \le 100$. Our job is to compute the sum of the odd numbers between $a$ and $b$, inclusive. The bounds are so small that almost any solution will be fast enough. We can simply loop from $a$ to $b$ 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 $2$, 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 $k$ is odd, then $k + 2$ is the next odd integer. With this in mind we can start at the smallest odd integer greater than or equal to $a$, and loop through each odd number until we reach $b$. And by the way, the smallest odd integer greater than or equal to $a$ is $a$ if $a$ is odd, and $a + 1$ if $a$ 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 $o_1$ denote the smallest odd integer greater than or equal to $a$, and let $o_n$ denote the largest odd integer less than or equal to $b$.

Then we can express this problem as an arithmetic series. Basically we are looking at the n-term arithmetic series $S_n = o_1 + o_2 + \dots + o_n$ where

$\displaystyle o_i = o_{i - 1} + 2 = o_1 + 2(i-1)$

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

$\displaystyle o_n = o_1 + 2(n - 1) \Leftrightarrow$
$\displaystyle o_n = o_1 + 2n - 2\Leftrightarrow$
$\displaystyle o_n - o_1 + 2 = 2n\Leftrightarrow$
$\displaystyle n = \frac{o_n - o_1 + 2}{2}$

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

$\displaystyle S_n = n\frac{o_1 + o_n}{2}$
which is an arithmetic sequence series difference $d = 2$ (see proof).

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 $n$ odd numbers is $n^2$. 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.