INSQ16A - Editorial

PROBLEM LINK:

Contest

Practice

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 :

  1. Sum of odd length sequence = Centre Elment * Length
  2. 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).

SOLUTION:

Tester’s Solution

Can’t access the solution, the page says access denied.alt text