最大子集，其没有可被K整除的和 [英] Maximum subset which has no sum of two divisible by K

问题描述

我给定集合{1，2​​，3，...，N}。我必须找到给定集合的子集的最大大小，使得来自子集的任何2个数字的总和不能被给定数字K除尽.N和K可以达到2 * 10 ^ 9，所以我需要一个非常快的算法。我只想出了一个复杂性O（K），这是慢的算法。

I am given the set {1, 2, 3, ... ,N}. I have to find the maximum size of a subset of the given set so that the sum of any 2 numbers from the subset is not divisible by a given number K. N and K can be up to 2*10^9 so i need a very fast algorithm. I only came up with an algorithm of complexity O(K), which is slow.

推荐答案

首先计算所有设置的元素mod k并解决简单问题：
找到最大大小子集，使得来自子集的任何2个数字的总和不等于给定数字K.
i将该集合划分为两个集合（i和ki），您不能选择集合（i）和set（ki）同时。

first calculate all of the set elements mod k.and solve simple problem: find the maximum size of a subset of the given set so that the sum of any 2 numbers from the subset is not equal by a given number K. i divide this set to two sets (i and k-i) that you can not choose set(i) and set(k-i) Simultaneously.

int myset[]
int modclass[k]

for(int i=0; i< size of myset ;i++)
{
    modclass[(myset[i] mod k)] ++;
}

选择

for(int i=0; i< k/2 ;i++)
{ 
    if (modclass[i] > modclass[k-i])
    {
        choose all of the set elements that the element mod k equal i
    }
    else
    {
        choose all of the set elements that the element mod k equal k-i
    }
}

最后，您可以从元素mod中添加一个元素k等于0或k / 2。

finally you can add one element from that the element mod k equal 0 or k/2.

此解决方案具有复杂度O（K）的算法。

this solution with an algorithm of complexity O(K).

您可以使用动态数组改进此主意：

you can improve this idea with dynamic array:

for(int i=0; i< size of myset ;i++)
{
    x= myset[i] mod k;
    set=false;
    for(int j=0; j< size of newset ;j++)
    {
        if(newset[j][1]==x or newset[j][2]==x)
        {
            if (x < k/2)
            {
                newset[j][1]++;
                set=true;
            }
            else
            {
                newset[j][2]++;
                set=true;
            }
        }
    }
    if(set==false)
    {
        if (x < k/2)
        {
            newset.add(1,0);
        }
        else
        {
            newset.add(0,1);
        }
    }
}

复杂度O（myset.count）的算法，你的算法比O（myset.count）更多，因为你需要O（myset.count）来读取你的集合。
这个解决方案的复杂度是O（myset.count ^ 2），你可以选择算法依赖你的input.with在O（myset.count ^ 2）和o（k）之间的比较。
和更好的解决方案，你可以排序myset基于mod k。

now you can choose with an algorithm of complexity O(myset.count).and your algorithm is more than O(myset.count) because you need O(myset.count) for read your set. complexity of this solution is O(myset.count^2),that you can choose algorithm depended your input.with compare between O(myset.count^2) and o(k). and for better solution you can sort myset based on mod k.

这篇关于最大子集，其没有可被K整除的和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！