Sum of the First n Odd Numbers
Problem
Print the sum 1 + 3 + 5 + ... of the first n odd numbers. For n = 4 the sum is 1 + 3 + 5 + 7 = 16.
Constraints
- 1 <= n <= 10^6
Examples
Input
4
Output
16
Solutions
Each new odd number is the border that turns a k by k square into a (k + 1) by (k + 1) square. So the total is n * n.
/*
* Problem : Sum of odd numbers.
* Input : n.
* Output : The sum.
* Approach: Square formula.
* Time : O(1)
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static long solve(long n) {
// Step 1: The sum of the first n odd numbers is always n * n (a square of dots grows by one odd border each time).
return n * n;
}
public static void main(String[] args) {
long n = new Scanner(System.in).nextLong();
System.out.println(solve(n));
}
}
Hints (2)
- What is 1 + 3 + 5?
- How does a square grow by an odd border?