专栏首页算法码上来每日算法系列【LeetCode 829】连续整数求和

每日算法系列【LeetCode 829】连续整数求和

题目描述

给定一个正整数 N ,试求有多少组连续正整数满足所有数字之和为 N ?

示例1

输入:
5
输出:
2
解释:
5 = 5 = 2 + 3,共有两组连续整数([5],[2,3])求和后为 5。

示例2

输入:
9
输出:
3
解释:
9 = 9 = 4 + 5 = 2 + 3 + 4

示例3

输入:
15
输出:
4
解释:
15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

提示

  • 1 <= N <= 10^9

题解

这是一道非常经典的数学题,挺基础的,不知道为什么这也能算困难难度的题目?

暴力法

遍历所有的连续数字区间 (i, j) ,然后求和看等不等于 N 。这种方法时间复杂度是 ,显然不可行。

暴力法优化

遍历所有的连续数字区间的左端点 i。然后假设区间长度为 n ,那么根据求和公式有 (2i+n-1)n/2=N ,然后只需要看这个方程的解是否是整数就行。时间复杂度可以降到 ,但还是太高了。

数学方法

根据上面的求和公式,对于起点 i 和长度 n ,求和得到 (2i+n-1)n/2=N 。我们可以先粗略推算一下 i 和 n 的范围,起点 i 的范围是 [1, N]毋庸置疑,而区间长度 n 的范围就可以考究一下了,一个出发点是:上面式子可以解出 i=(N-n(n-1)/2)/n ,而 i>=1 ,可以解出 (n+1)n<=2N ,所以 n 的范围其实只有根号 N 级别,可以直接遍历。另一个出发点是最小的 n 个数加起来就是 1 加到 n 等于 n(n+1)/2 ,这个要小于等于 N ,解出来也是 (n+1)n<=2N 。

所以我们只需要从 1 开始遍历 n ,直到 (n+1)n>2N 为止,然后判断 (N-n(n-1)/2)/n 是否是整数就行了(前面终止条件可以保证 i 一定大于 0 )。

最终时间复杂度降到了 。

代码

数学方法(c++)

class Solution {
public:
    int consecutiveNumbersSum(int N) {
        int res = 0;
        for (int n = 1; (n + 1) * n <= 2 * N; ++n) {
            if ((N - n * (n - 1) / 2) % n == 0) res++;
        }
        return res;
    }
};

数学方法(python)

class Solution:
    def consecutiveNumbersSum(self, N: int) -> int:
        res = 0
        for n in range(1, N+1):
            if n * (n + 1) > 2 * N:
                break
            if (N - n * (n - 1) // 2) % n == 0:
                res += 1
        return res

后记

这题还可以用质因数分解等方法进一步优化,但是没有必要。

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每日算法系列【EOJ 3031】二进制倒置

    给定一个整数 、将 的 334 位二进制表示形式(不包括开头可能的值为 0 的位, 表示为 1 位 0)前后倒置,输出倒置后的二进制数对应的整数。

    godweiyang
  • 【每日算法Day 63】LeetCode 第 179 场周赛题解

    https://leetcode-cn.com/problems/generate-a-string-with-characters-that-have-odd...

    godweiyang
  • 【每日算法Day 94】经典面试题:机器人的运动范围

    地上有一个 m 行 n 列的方格,从坐标 [0, 0] 到坐标 [m-1, n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、...

    godweiyang
  • 挑战程序竞赛系列(80):4.3 2-SAT(4)

    挑战程序竞赛系列(80):4.3 2-SAT(4) 传送门:POJ 2749: Building roads 题意: 阳关路与独木桥:有N个农场,其中A对相...

    用户1147447
  • 洛谷P4555 [国家集训队]最长双回文串(manacher 线段树)

    我的做法比较naive。。首先manacher预处理出以每个位置为中心的回文串的长度。然后枚举一个中间位置,现在要考虑的就是能覆盖到i - 1的回文串中 中心最...

    attack
  • 数字问题-LeetCode 524、525、526、528、530、537、539、540

    LeetCode # 524 525 526 528 530 537 539 540

    算法工程师之路
  • 4.7字符串匹配(3)

    用户1147447
  • SDOI 2018二轮题解(除Day2T1)

    然鹅学了不到一个月文化课再回来看OI的东西有一种恍如隔世的感觉,烤前感觉也没啥可复习的,就补一补去年二轮的题吧。

    attack
  • 洛谷P4783 【模板】矩阵求逆(高斯消元)

    attack
  • ZROJ#397. 【18提高7】模仿游戏(爆搜)

    读完题目后不难发现,每次约束的条件相当于是\(b[((x[i] + i) % N + (i / N) % N) % N] = y[i]\)

    attack

扫码关注云+社区

领取腾讯云代金券