PROBLEM LINK:
Author: Amit Raj
Tester: Vikash Dubey
Editorialist: Vikash Dubey
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
Given N, you have to tell whether there exists a continuous sequence of natural numbers less than such that the sum of the numbers of the sequence is N.
EXPLANATION:
If N is a power of 2 then answer is NO otherwise YES.
Formula :
- Sum of odd length sequence = Centre Elment * Length
- Sum of even length sequence = (sum of 2 Centre Elements) * length / 2
As sum of any 2 consecutive numbers is always odd and greater than 1, sum of any sequence will have an odd divisor greater than 1.
Case 1 :
N is power of 2 :
As sum of any 2 consecutive numbers is always odd and greater than 1, sum of any even length sequence will have an odd divisor greater than 1. Also odd length sequence has an odd divisor.
But any power of 2 (except 1) have no odd divisor greater than 1, so the answer is NO.
Case 2 :
N is not a power of 2 :
In this case N must have some odd divisor greater than 1.
So we can always find a sequence with even length(if N = 2 * prime greater than 2, centres will be prime / 2 and prime / 2 + 1) or odd length(with centre N / smallest prime divisor greater than 2).
