PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Abhinav Gupta
Testers: Nishank Suresh, Tejas Pandey
Editorialist: Nishank Suresh
DIFFICULTY:
1044
PREREQUISITES:
None
PROBLEM:
Given N, count the number of pairs (A, B) such that 1 \leq A, B \leq N and A+B is odd.
EXPLANATION:
For A+B to be odd, one of A must be odd and the other must be even. In fact, this is the only restriction.
So, to count the total number of pairs:
- Let the number of even numbers from 1 to N be E, and the number of odd numbers from 1 to N be O.
- If A is odd and B is even, we have O\cdot E choices for them (O for A and E for B)
- If A is even and B is odd, we have E\cdot O choices for them.
- So, the total number of choices is 2\cdot E \cdot O.
All that remains is to find E and O quickly. This is quite easy:
-
O = \left\lceil \frac{N}{2}\right\rceil, which can be implemented in most languages as
(N+1)/2
, using integer division. -
E = \left\lfloor \frac{N}{2}\right\rfloor, which can be implemented in most languages as simply
N/2
using integer division
Note that N \leq 10^9, so the answer can exceed the range of 32-bit integers. Make sure to use a 64-bit integer datatype.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
odds, evens = (n+1)//2, n//2
print(2*odds*evens)