We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Non-Divisible Subset
Non-Divisible Subset
+ 0 comments In the first example, S=[19, 10, 12, 10, 24, 25, 22] is invalid right? In the input format section. It's said that all of the given numbers are distinct. So the 10 value shouldn't appear more than once.
+ 0 comments C# solution
public static int nonDivisibleSubset(int k, List<int> s) { int[] remainders = new int[k]; foreach (int num in s) { int remainder = num % k; remainders[remainder]++; } int count = Math.Min(remainders[0], 1); for (int i = 1; i <= k / 2; i++) { if (i != k - i) { count += Math.Max(remainders[i], remainders[k - i]); } else if (remainders[i] > 0) { count++; } } return count; }
+ 0 comments C++ code
int nonDivisibleSubset(int k, vector<int> s) { vector<long> arr(k,0); for(int i = 0; i < s.size(); i++){ arr[s[i] % k]++; } long sum = 0; if (k == 1){sum = 1; goto END;} if (k == 2){sum = 2; goto END;} if (k % 2 == 0){ if (arr[0] > 1) sum = sum + 1; if (arr[k/2] > 1) sum = sum + 1; for (long i = 1; i < k/2; i++){ if (arr[i] > arr[k-i]){sum = sum + arr[i];} else {sum = sum + arr[k-i];} } } else { if (arr[0] > 1) sum = sum + 1; for (long i = 1; i < (k+1)/2; i++){ if(arr[i] > arr[k-i]){sum = sum + arr[i];} else {sum = sum + arr[k-i];} } } END: return sum; }
+ 0 comments // k = 4, s = [1 1 1 2 2 3 3 3 3 4 4] // only 3 cases: // 1) we have 4 in s, we can take only one // 2) we can take only one 2, if it exists // 3) we can take 1 or 3, but not together, // 4 of "3" is bigger than 3 of "1", we take 4 of "3" int res = 0; int[] modK = new int[k]; for (int el : s) { modK[el % k]++; } // we can take only one 4 if it exists if (modK[0] > 0) { res = 1; } // start with 1 because we counted modK[0] before for (int i = 1; i < k; i++) { // if no numbers, just miss if (modK[i] == 0) { continue; } // we can take only one 2 if it exists if (2 * i == k) { res++; } else { // we take 4 of "3", because it is bigger than 3 of "1" res += Math.max(modK[i], modK[k - i]); // make them zero, not to count twice modK[i] = 0; modK[k - i] = 0; } } return res;
+ 0 comments Efficient solution implemented in Python3
def nonDivisibleSubset(k, s): if k ==1: return 1 #first exception res = [x%k for x in s] #array of residues mod k recurrence = dict([(x,0) for x in range(k)]) #dict for saving recurrence of residues in array s for i in range(len(res)): recurrence[res[i]] += 1 result = 0 if recurrence[0]>0: result += 1 #Add one multiple of k, if exists if k <=3:#Two more special cases if k == 2 and recurrence[1]: result += 1 else: result += max(recurrence[1],recurrence[2]) return result for x in range(1,k//2): result += max(recurrence[x],recurrence[k-x]) if k%2 == 0 and recurrence[k/2] > 0: result += 1 else: result += max(recurrence[k//2],recurrence[k - k//2]) return result
Load more conversations
Sort 681 Discussions, By:
Please Login in order to post a comment