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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Non-Divisible Subset

Non-Divisible Subset

Problem
Submissions
Leaderboard
Discussions
Editorial

Given a set of distinct integers, print the size of a maximal subset of where the sum of any numbers in is not evenly divisible by .

Example

One of the arrays that can be created is . Another is . After testing all permutations, the maximum length solution array has elements.

Function Description

Complete the nonDivisibleSubset function in the editor below.

nonDivisibleSubset has the following parameter(s):

  • int S[n]: an array of integers
  • int k: the divisor

Returns

  • int: the length of the longest subset of meeting the criteria

Input Format

The first line contains space-separated integers, and , the number of values in and the non factor.
The second line contains space-separated integers, each an , the unique values of the set.

Constraints

  • All of the given numbers are distinct.

Sample Input

STDIN    Function
-----    --------
4 3      S[] size n = 4, k = 3
1 7 2 4  S = [1, 7, 2, 4]

Sample Output

3

Explanation

The sums of all permutations of two elements from are:

1 + 7 = 8
1 + 2 = 3
1 + 4 = 5
7 + 2 = 9
7 + 4 = 11
2 + 4 = 6

Only will not ever sum to a multiple of .

Author

zxqfd555

Difficulty

Medium

Max Score

20

Submitted By

116053

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy