CODEWITHSUNDEEP
python
Diwakar SHARMA
Diwakar SHARMA

Reputation: 581

Non Divisible subset in python

I have been given a set S, of n integers, and have to print the size of a maximal subset S' of S where the sum of any 2 numbers in S' are not evenly divisible by k.

Input Format

The first line contains 2 space-separated integers, n and k, respectively. The second line contains n space-separated integers describing the unique values of the set.

My Code :

import sys


n,k = raw_input().strip().split(' ')
n,k = [int(n),int(k)]
a = map(int,raw_input().strip().split(' '))
count = 0


for i in range(len(a)):
    for j in range(len(a)):
        if (a[i]+a[j])%k != 0:
            count = count+1

print count

Input:

4 3
1 7 2 4

Expected Output:

3

My Output:

10

What am i doing wrong? Anyone?

Upvotes: 0

Views: 4776

Answers (4)

niken
niken

Reputation: 2611

Java solution

public class Solution {

    static PrintStream out = System.out;

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner (System.in);
        int n = in.nextInt();
        int k = in.nextInt();        
        int[] A = new int[n];

        for(int i=0;i<n;i++){
            A[i]=in.nextInt();
        }

        int[] R = new int[k];
        for(int i=0;i<n;i++)            
            R[A[i] % k]+=1;

        int res=0;
        for(int i=0;i<k/2+1;i++){
            if(i==0 || k==i*2)
                res+= (R[i]!=0)?1:0;
            else
                res+= Math.max(R[i], R[k-i]);            
        }

        out.println(res);
    }
}

Upvotes: 0

Doogle
Doogle

Reputation: 1264

Yes O(n) solution for this problem is very much possible. Like planetp rightly pointed out its pretty much the same solution I have coded in java. Added comments for better understanding.

import java.io.; import java.util.;

public class Solution {

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n=in.nextInt();
    int k=in.nextInt();
    int [] arr = new int[k];
    Arrays.fill(arr, 0);
    Map<Integer,Integer> mp=new HashMap<>();

Storing the values in a map considering there are no duplicates. You can store them in array list if there are duplicates. Only then you have different results. for(int i=0;i 

    int res=0;

    for(int i=0;i<=(k/2);i++)
    {
        if(i==0 || k==i*2)
        {
            if(arr[i]!=0)
               res+=1;
        }

If the no. is divisible by k we can have only one and if the no is exactly half of k then we can have only 1. Rational if a & b are divisble by k then a+b is also divisible by k. Similarly if c%k=k/2 then if we have more than one such no. their combination is divisible by k. Hence we restrict them to 1 value each. else { int p=arr[i]; int q=arr[k-i]; if(p>=q) res+=p; else res+=q; }

This is simple figure out which is more from a list of 0 to k/2 in the list if a[x]>a[k-x] get the values which is greater. i.e. if we have k=4 and we have no. 1,3,5,7,9,13,17. Then a[1]=4 and a[3]=2 thus pick a[1] because 1,5,13,17 can be kept together.

    }   
       System.out.println(res);
    }
}

Upvotes: 2

planetp
planetp

Reputation: 16113

You can solve it in O(n) time using the following approach:

L = [0]*k

for x in a: 
    L[x % k] += 1
res = 0
for i in range(k//2+1):
    if i == 0 or k == i*2:
        res += bool(L[i])
    else:
        res += max(L[i], L[k-i])

print(res)

Upvotes: 16

Luis Masuelli
Luis Masuelli

Reputation: 12343

# given k, n and a as per your input.
# Will return 0 directly if n == 1
def maxsize(k, n, a):
    import itertools
    while n > 1:
        sets = itertools.combinations(a, n)
        for set_ in sets:
            if all((u+v) % k for (u, v) in itertools.combinations(set_, 2)):
                return n
        n -= 1
    return 0

Upvotes: 1

Related Questions