首页 > 试题广场 >

牛牛的两个集合

[编程题]牛牛的两个集合
  • 热度指数：264 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛牛想把中的自然数分别放到两个集合中，但是他想使这两个集合中元素之和的差的绝对值最小，牛牛不知道该怎么做，所以他想请你帮忙。
给定一个数n，返回分成两个集合后，这两个集合中元素之和的差的绝对值最小是多少？
示例1

输入

2

输出

1

说明

分成两个集合，其中的元素分别为1和2，那么其差为1。

备注:
算法知识视频讲解
添加回答
牛客471841957号头像 牛客471841957号
通过全部用例
运行时间52ms
占用内存8060KB 

function findNumber( n ) {
    const remainder = n % 4
    if(remainder === 0 || remainder === 3) {
        return 0
    } else {
        return 1
    }
}
module.exports = {
    findNumber : findNumber
};

每4个连续自然数，连续取头尾做和可以得到偶数个一样大的和，将这些和对半分给两个集合，他们作差刚好等于0。
例如 1234 连续取头尾可得 1+4、2+3，2个（偶数个）一样大的和；23456789可以得2+9、3+8、4+7、5+6，4个（偶数个）一样大的和，对半分作差等于0。
我们从右边取成4倍数最多的自然数，分别分给两个集合，这部分数刚好抵消。余下的数只有4中情况：
余下1,2,3（n%4===3）  作差最小绝对值=0
余下1,2（n%4===2） 作差最小绝对值=1
余下1（n%4===1）作差最小绝对值=1
无余下的数字（n%4===0）作差最小绝对值=0
所以n%4等于3和0时差绝对值=0，其他情况=1
发表于 2022-01-02 18:05:49 回复(0)
牛客377646584号头像 牛客377646584号
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 给定一个数n，返回分成两个集合后，这两个集合中元素之和的差的绝对值最小是多少？
# @param n int整型 代表题意中的n
# @return int整型
#
class Solution:
    def findNumber(self , n ):
        # write code here
        
        if n%4<=2 and n%4>0:
            return 1
        else:
            return 0
发表于 2021-04-23 11:14:47 回复(0)
spongebob7头像 spongebob7
class Solution:
    def findNumber(self , n ):
        if n%2==0:
            if (n/2)% 2 ==0:
                return 0
            else:
                return 1
        else:
                if ((n-1)/2)% 2 ==0:
                    return 1
                else:
                    return 0
每两个连续的数字之差为1
对于偶数个连续数字
将连个连续数字配对，存在奇数数字对和偶数数字对
偶数数字对配凑成加一减一就是0，奇数数字对多出一对就算差值为1
对于奇数个连续数字
先把n-1偶数部分配凑，取n/2的整数部分，将n加入有n/2的集合，则两者差1，在偶数数字对就是1，奇数数字对可以把两个差值1配凑消去为0
发表于 2021-03-05 14:55:40 回复(0)
提交观点

问题信息

模拟
难度：
3条回答 1471浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号