Sum of Even or Odd Numbers
Description
Given an integer n and a word parity, "even" or "odd", return the sum of the even numbers from 1 to n when parity is "even", and the sum of the odd numbers from 1 to n when it is "odd". n itself counts when it is of that kind.
Examples
Example 1
Input: n = 10, parity = "even"
Output: 30
Explanation: 2 + 4 + 6 + 8 + 10 = 30.
Example 2
Input: n = 10, parity = "odd"
Output: 25
Explanation: 1 + 3 + 5 + 7 + 9 = 25.
Example 3
Input: n = 1, parity = "even"
Output: 0
Explanation: There's no even number from 1 to 1, so the sum is 0.
Example 4
Input: n = 7, parity = "odd"
Output: 16
Explanation: 1 + 3 + 5 + 7 = 16: 7 counts, since it's odd and n is 7.
Constraints
- 1 ≤ n ≤ 10^5
parityis"even"or"odd"
Editorial
Brute Force - Add Every Other Number
Intuition
Even numbers are every other number starting from 2, and odd ones every other number starting from 1. So start at the first one of the right kind, step by 2 up to n, and add as you go.
The odd numbers up to 100,000 add up to 2,500,000,000, past the largest int, 2,147,483,647: keep the total in a long in Java and a long long in C++.
Step-by-Step Explanation
Let's trace Example 1, n = 10, parity = "even":
- Start at 2 and step by 2: 2, 4, 6, 8, 10.
- Add each to the total: 2 + 4 + 6 + 8 + 10 = 30.
- Return
30.
Every Other Number — The even numbers up to 10, added one at a time.
Algorithm
- Start at 2 for
"even"and at 1 for"odd". - Add each number from there to
n, stepping by 2. - Return the total.
Code
class Solution {
public:
long long sumOfEvenOrOdd(int n, string& parity) {
long long total = 0; // long long: the sum can pass the int range
for (int x = parity == "even" ? 2 : 1; x <= n; x += 2) total += x;
return total;
}
};
class Solution:
def sumOfEvenOrOdd(self, n: int, parity: str) -> int:
total = 0
start = 2 if parity == "even" else 1
for x in range(start, n + 1, 2): # every other number, from the first of the right kind
total += x
return total
class Solution {
public long sumOfEvenOrOdd(int n, String parity) {
long total = 0; // long: the sum can pass the int range
for (int x = parity.equals("even") ? 2 : 1; x <= n; x += 2) total += x;
return total;
}
}
var sumOfEvenOrOdd = function(n, parity) {
let total = 0;
for (let x = parity === "even" ? 2 : 1; x <= n; x += 2) total += x;
return total;
};
Complexity Analysis
Time Complexity: O(n)
It visits n / 2 numbers.
Space Complexity: O(1)
One running total.
Why This Approach Is Not Efficient
Here it's all you need: at most 50,000 additions. But its time grows with n. On our judge the loop took 315 ms for n = 10,000,000 and 2.92 s for n = 100,000,000 in Python: ten times the numbers, 9 times the time. These numbers follow a pattern, though, so the sum can be worked out without visiting them.
Optimal Approach - A Formula for the Sum
Intuition
The even numbers up to n are 2 × 1, 2 × 2, ..., 2 × m, where m = n // 2. Their sum is 2 × (1 + 2 + ... + m), and 1 + 2 + ... + m is m × (m + 1) / 2, so the even sum is m × (m + 1).
The odd numbers up to n are the first m = (n + 1) // 2 odd numbers, and those always add up to m × m: 1 = 1, 1 + 3 = 4, 1 + 3 + 5 = 9, and so on.
Step-by-Step Explanation
Let's trace the same example, n = 10, parity = "even":
m = 10 // 2 = 5: the even numbers up to 10 are 2 × 1, 2 × 2, ..., 2 × 5.- So their sum is 2 × (1 + 2 + ... + 5) = 2 × 15 =
m × (m + 1)= 30. - Return
30.
Count Them, Then Multiply — The even numbers up to 10 counted, then added with one multiplication.
Algorithm
- For
"even":m = n // 2; returnm * (m + 1). - For
"odd":m = (n + 1) // 2; returnm * m.
Code
On our judge it took 28 ms for n = 100,000,000 in Python, the same as for any other n.
class Solution {
public:
long long sumOfEvenOrOdd(int n, string& parity) {
if (parity == "even") {
long long m = n / 2; // 2, 4, ..., 2m: m numbers
return m * (m + 1); // 2 × (1 + 2 + ... + m)
}
long long m = (n + 1) / 2; // 1, 3, ..., 2m - 1: m numbers
return m * m; // the first m odd numbers add up to m × m
}
};
class Solution:
def sumOfEvenOrOdd(self, n: int, parity: str) -> int:
if parity == "even":
m = n // 2 # 2, 4, ..., 2m: m numbers
return m * (m + 1) # 2 × (1 + 2 + ... + m)
m = (n + 1) // 2 # 1, 3, ..., 2m - 1: m numbers
return m * m # the first m odd numbers add up to m × m
class Solution {
public long sumOfEvenOrOdd(int n, String parity) {
if (parity.equals("even")) {
long m = n / 2; // 2, 4, ..., 2m: m numbers
return m * (m + 1); // 2 × (1 + 2 + ... + m)
}
long m = (n + 1) / 2; // 1, 3, ..., 2m - 1: m numbers
return m * m; // the first m odd numbers add up to m × m
}
}
var sumOfEvenOrOdd = function(n, parity) {
if (parity === "even") {
const m = Math.floor(n / 2); // 2, 4, ..., 2m: m numbers
return m * (m + 1); // 2 × (1 + 2 + ... + m)
}
const m = Math.floor((n + 1) / 2); // 1, 3, ..., 2m - 1: m numbers
return m * m; // the first m odd numbers add up to m × m
};
Complexity Analysis
Time Complexity: O(1)
One multiplication, whatever n is.
Space Complexity: O(1)
Nothing is stored.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Keeping the total in an int. int total = 0;
On n = 100000, parity = "odd" it returns -1794967296 in Java; the answer is 2500000000. The odd numbers up to 100,000 add up to 2,500,000,000, more than the largest int, 2,147,483,647. An int total wraps around to a negative number; keep it in a long.
Stopping before n. range(start, n, 2)
On n = 10, parity = "even" it returns 20; the answer is 30. range(start, n, 2) leaves n out, so when n itself is even (or odd) it's missing from the sum. The end has to be n + 1.
Mixing up even and odd. want = 1 if parity == "even" else 0
On n = 10, parity = "even" it returns 25; the answer is 30. Even numbers leave a remainder of 0 when divided by 2, and odd ones 1. With the two swapped, the even sum comes out as the odd one and the other way round.
Where This Pattern Is Taught
This problem practises a loop that steps by 2, and a total that outgrows int. It's taught in Java for DSA and C++ for DSA.