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

  • Thread starter Thread starter SlurrerOfSpeech
  • Start date Start date
  • Tags Tags
    Sum
Click For Summary
SUMMARY

The discussion centers on a C# solution for finding the largest subset of integers from a given set such that the sum of every pair does not divide a specified integer K. The user encountered issues with test cases due to a misunderstanding of the Skip method in LINQ, which led to incorrect subset generation. The solution iterates through the set and checks pairwise sums, but the logic fails to account for proper indexing and subset formation. The final output is the maximum size of the valid subset.

PREREQUISITES
  • C# programming language proficiency
  • Understanding of LINQ methods, specifically Skip and All
  • Knowledge of subset generation algorithms
  • Familiarity with modular arithmetic concepts
NEXT STEPS
  • Review C# LINQ documentation for advanced usage of Skip and All
  • Study subset generation techniques in algorithm design
  • Learn about modular arithmetic and its applications in programming
  • Explore optimization strategies for combinatorial problems
USEFUL FOR

Software developers, particularly those working with C# and algorithm design, as well as anyone interested in solving combinatorial problems involving modular arithmetic.

SlurrerOfSpeech
Messages
141
Reaction score
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
Ah, nevermind. Skip doesn't do what I thought it does.
 
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.
 

Similar threads

  • · Replies 9 ·
Replies
9
Views
3K
  • · Replies 10 ·
Replies
10
Views
2K
  • · Replies 9 ·
Replies
9
Views
2K
  • · Replies 3 ·
Replies
3
Views
3K
  • · Replies 13 ·
Replies
13
Views
5K
  • · Replies 3 ·
Replies
3
Views
2K
Replies
3
Views
1K
Replies
2
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K