UVa 10783: Odd Sum

UVa 10783: Odd Sum

Written by on 13 June 2012

Topics: UVa Online Judge

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:

which is an arithmetic sequence series difference (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 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.

2 Comments For This Post I'd Love to Hear Yours!

  1. Eman says:

    Nice :D

  2. snnn says:

    Only two lines:
    const int n=(end-start)>>1;
    result=start*(n+1) + n*(n+1);

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.