Problem Setter : Ashish Khatkar
Problem Tester : Aneesh Dogra
Editorialist : Mohit Wadhwa
Contest link : POWER2
Practice link : POWER2
Problem simply asked that whether a given number can be expressed as sum of powers of 2 where a condition was put that the power should be a non zero positive integer.
Now suppose we are given number 2 then it can expressed as 2 raised to the power 1 so 2 can be expressed as sum of powers of 2 hence it is a magical number. Similarly all even numbers are magical number as they can be formed by summing up n/2 2’s. Now if we take number 1 then it can be expressed as 2 raised to the power 0 but it is clearly mentioned that power should be non zero positive integer so 1 is not a magical number. Similarly all the odd integers can’t be expressed as sum of powers of 2. Now a corner case is that if we take number 0 then it is even but we cannot form 0 by sum of powers of 2. Therefore, 0 is not a magical number. Finally the result is that all even numbers except 0 are magical numbers.