Largest subset whose every pair's sum doesn't divide K

  • Thread starter SlurrerOfSpeech
  • Start date
  • Tags
    Sum
In summary, the conversation is about a person seeking help with their code, specifically with passing test cases. They thought their solution was straightforward but it was failing some test cases. They then mention using a skip function but realizing it doesn't do what they thought it did. The person responding adjusted the code tags for better syntax highlighting and mentions that they assumed the programming language was C#. The original person then says they found their answer.
  • #1
SlurrerOfSpeech
141
11
Any idea where I'm going wrong here? It's failing some test cases. I thought my solution was straightforward (if not brute force).

Code:
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution
{
    static void Main(String[] args)
    {
        int k = Int32.Parse(Console.ReadLine().Split(' ')[1]);
        var S = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
      
        int max = Int32.MinValue;
        foreach(int i in S)
        {
            var ss = new List<int>() { i };
            foreach(int j in S.Skip(i))
                if(ss.All(m => (m + j) % k != 0))
                    ss.Add(j);
            if(ss.Count > max)
                max = ss.Count;
        }
          
        Console.WriteLine(max);
    }
}
 
Last edited by a moderator:
Technology news on Phys.org
  • #2
Ah, nevermind. Skip doesn't do what I thought it does.
 
  • #3
Ok, I couldn't decide what programming language you were using, I assumed it was C#.

Anyway I adjusted your code tags to turn on syntax highlighting ie CODE=JAVA or CODE=PYTHON ... C# and C++ revert to C.

Glad you found your answer.
 

1. What is the definition of "Largest subset whose every pair's sum doesn't divide K"?

The "Largest subset whose every pair's sum doesn't divide K" refers to finding the largest possible subset of a given set of numbers, where the sum of any two numbers in the subset does not divide a given number K.

2. How is this problem typically solved?

This problem is typically solved using algorithms such as dynamic programming or backtracking, as it involves finding the largest possible subset with a specific constraint.

3. What is the significance of this problem in the field of computer science?

This problem is significant in the field of computer science as it is a classic example of a combinatorial optimization problem, which has many real-world applications such as resource allocation, scheduling, and network routing.

4. Can this problem be solved in polynomial time?

No, this problem is considered to be NP-hard, which means that it cannot be solved in polynomial time for all inputs. However, efficient approximation algorithms can be used to find a solution that is close to the optimal solution.

5. Are there any variations of this problem?

Yes, there are variations of this problem such as finding the largest subset whose every pair's sum is not a multiple of K or finding the largest subset whose every pair's sum is not a factor of K. These variations have different solutions and complexities.

Similar threads

  • Programming and Computer Science
Replies
9
Views
2K
  • Programming and Computer Science
Replies
10
Views
1K
  • Programming and Computer Science
Replies
9
Views
1K
  • Programming and Computer Science
Replies
3
Views
2K
  • Programming and Computer Science
Replies
13
Views
4K
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
3
Views
885
  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Programming and Computer Science
Replies
2
Views
2K
  • Programming and Computer Science
Replies
2
Views
1K
Back
Top