# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

* Author:* Rahul Kumar

*Danny Mittal*

**Tester:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

SImple

# PREREQUISITES:

None

# PROBLEM:

Given N, consider all arrays of length N consisting of non-negative and distinct integers whose prefix sums are all odd. Output the minimum sum of elements of such an array.

# QUICK EXPLANATION

One possible array is A = [1, 0, 2, 4, \dots, 2N-2], whose sum is 1 + (N-1)(N-2).

# EXPLANATION:

First, note that the condition on all prefix sums being odd tells us that:

- A_1 is odd
- A_i is even for i > 1

There is only one odd number in the array, and we want to minimize the total sum. It is thus optimal to choose the smallest odd integer we can; that being 1.

The remaining N-1 elements must all be even and distinct. Once again, it is obviously optimal to choose the smallest N-1 even elements we can, which turns out to be \{0, 2, 4, 6, \dots, 2N - 4\}.

Now we know all the elements of the array, all that remains is to find their sum. Note that

So, the final answer turns out to be 1 + (N-2)(N-1).

###
A lesson about `endl`

This problem had rather high constraints - in most languages, the default method of taking input and printing output will likely time out, and the statement had a note asking participants to use faster methods.

However, there is one more pitfall here, specifically in `C++`

- and that is the use of `endl`

.

The standard way of speeding up i/o in `C++`

via adding the lines

```
ios::sync_with_stdio(0);
cin.tie(0);
```

speeds up output by ensuring that the output buffer is not flushed every time `cin`

is called (which is what `cin.tie(0)`

does).

However, `endl`

always forces a flush of the buffer, so using it essentially nullifies any benefit you had in the first place.

The workaround is to always use `\n`

instead of `endl`

.

# TIME COMPLEXITY:

\mathcal{O}(1) per test.

# CODE:

## Setter (C++)

```
#include<bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define vi vector<int>
#define w(x) int x; cin>>x; while(x--)
#define pb push_back
int32_t main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
fio
w(t)
{
int n;
cin>>n;
cout<<(n-1)*(n-2)+1<<"\n";
}
}
```

## Tester (Kotlin)

```
import java.io.BufferedInputStream
fun main(omkar: Array<String>) {
val jin = FastScanner()
val out = StringBuilder()
repeat(jin.nextInt(1000000)) {
val n = jin.nextInt(1000000000).toLong()
val answer = ((n - 1L) * (n - 2L)) + 1L
out.appendln(answer)
}
print(out)
jin.assureInputDone()
}
class FastScanner {
private val BS = 1 shl 16
private val NC = 0.toChar()
private val buf = ByteArray(BS)
private var bId = 0
private var size = 0
private var c = NC
private var `in`: BufferedInputStream? = null
constructor() {
`in` = BufferedInputStream(System.`in`, BS)
}
private val char: Char
private get() {
while (bId == size) {
size = try {
`in`!!.read(buf)
} catch (e: Exception) {
return NC
}
if (size == -1) return NC
bId = 0
}
return buf[bId++].toChar()
}
fun assureInputDone() {
if (char != NC) {
throw IllegalArgumentException("excessive input")
}
}
fun nextInt(endsLine: Boolean): Int {
var neg = false
c = char
if (c !in '0'..'9' && c != '-' && c != ' ' && c != '\n') {
throw IllegalArgumentException("found character other than digit, negative sign, space, and newline")
}
if (c == '-') {
neg = true
c = char
}
var res = 0
while (c in '0'..'9') {
res = (res shl 3) + (res shl 1) + (c - '0')
c = char
}
if (endsLine) {
if (c != '\n') {
throw IllegalArgumentException("found character other than newline")
}
} else {
if (c != ' ') {
throw IllegalArgumentException("found character other than space")
}
}
return if (neg) -res else res
}
fun nextInt(from: Int, to: Int, endsLine: Boolean = true): Int {
val res = nextInt(endsLine)
if (res !in from..to) {
throw IllegalArgumentException("$res not in range $from..$to")
}
return res
}
fun nextInt(to: Int, endsLine: Boolean = true) = nextInt(1, to, endsLine)
}
```

## Editorialist (Python)

```
import sys
input = sys.stdin.readline
for _ in range(int(input())):
n = int(input())
print(1 + (n-1)*(n-2))
```