日行一算(Consecutive Integer-连续整数)

题目

题目描述
2005年的百度之星初赛有这么一道题,一个正整数有可能可以被表示为 m(m>1) 个连续正整数之和,如:

15=1+2+3+4+5
15=4+5+6
15=7+8

但现在你的任务是判断给定的整数n能否表示成连续的m(m>1)个正整数之和。

解答要求
时间限制:1000ms, 内存限制:100MB
输入
输入只有一个整数n (1<n<230 +1)。

输出
若n能表示成连续的m(m>1)个正整数之和则输出“YES”,否则输出“NO”。

解题思路

分析:Java递归

  1. 初看这道题时,只觉得不需思考,循环就可以解决
    思路:嵌套循环,逐项相加,当前n项和大于目标值,则减去左侧小的值使和小于目标值,再继续如此,直到等于目标值或循环结束。
    最终在百万级别超时。
  2. 此时意识到双重循环耗时严重,需分析算法再进行求解
    思路:连续数相当于等差数列,差为1,利用前n项和公式,使其等于目标值,根据项数不同,只要能求出首项为整数即可。
    最终在十亿级别超时。
  3. 终于,这个数量级已经不是循环能搞定的了,必须在数学层面想点别的招了
    思路:
    奇数,一个奇数n可表示为(n+1)/2,(n-1)/2.所以奇数必然可以写成连续数。奇数的倍数是只需要在原有奇数序列两端不停的+1-1即可,直到左侧最小数变成0,此时为(n-n)/2,同时可以发现最大数为n,此时连续个数=奇数值,以后无论多少倍,在基础上加相应倍数即可。(例7:3,4 翻倍14:2,3,4,5 再翻28:0,1,2,3,4,5,6,7 此时除去0,个数与奇数值相同,无论在以后怎么加都ok)
    那就简单了,目标数字能够除以2,最终是奇数即可(除了1),你想想是不是只有2的n次方不满足条件。
    所以这道题的意义就是判断输入是否为2的n次方。
public class Main {
    public static void main(String[] args) {      
        System.out.println(method(new Scanner(System.in).nextInt()));
    }
    
    private static String method(int num){
        if(num == 1){
            return "NO";
        }
        if(num %2 !=0 ){
            return "YES";
        }
        return method(num/2);
    }
}