[해커랭크] Non-Divisible Subset

[해커랭크] Non-Divisible Subset

 

https://www.hackerrank.com/challenges/non-divisible-subset/problem?isFullScreen=true

Non-Divisible Subset | HackerRank

 

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.아래 편집기에서 non DivisibleSubset 함수를 완성하세요.

nonDivisibleSubset has the following parameter(s):nonDivisibleSubset은 다음과 같은 매개변수를 가집니다:

• int S[n]: an array of integersint S[n]: 정수 배열입니다
• int k: the divisor Int K: 약수(divisor)

Returns반환

• int: the length of the longest subset of  meeting the criteriaint: 기준을 충족하는 가장 긴 부분집합의 길이

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.첫 번째 줄은 공간 분리 정수와 , 의 값 수, 그리고 비인수(non factors)를 포함한다. 두 번째 줄은 공간 구분된 정수로 구성되며, 각 는 집합의 고유 값이다.

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 .단, 의 배수로 합이 되는 것은 절대 아닙니다.

 

 

 

 

주석 보다시피 케이스는 3가지

나머지가 0, k/2, i vs k-i 일때의 규칙 외에는 서로 합해서 k가 되는 조합이 없음.

import java.io.*;

import java.math.*;

import java.security.*;

import java.text.*;

import java.util.*;

import java.util.concurrent.*;

import java.util.function.*;

import java.util.regex.*;

import java.util.stream.*;

import static java.util.stream.Collectors.joining;

import static java.util.stream.Collectors.toList;

class Result {

    /*

     * Complete the 'nonDivisibleSubset' function below.

     *

     * The function is expected to return an INTEGER.

     * The function accepts following parameters:

     *  1. INTEGER k

     *  2. INTEGER_ARRAY s

     */

    public static int nonDivisibleSubset(int k, List<Integer> s) {

    // Write your code here

   

        // 19 10 12 10 24 25 22, 4

        //  3  2  0  2  0  1  2

        int dap = 0;

        int[] modCnt = new int[k];

       

        for(int num : s){

            modCnt[num%k]++;

        }

       

        // 0 0

        if(modCnt[0] > 0){ dap++; } // zero only +1

       

        // 1 2 2 2 3

        for(int i=1; i<=(k/2); i++){

            if(i == k-i ){

                dap++;  // only +1

            }else{

                // choose max

                dap += Math.max(modCnt[i], modCnt[k-i]);

            }

        }

       

       

        return dap;

    }

}

public class Solution {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int n = Integer.parseInt(firstMultipleInput[0]);

        int k = Integer.parseInt(firstMultipleInput[1]);

        List<Integer> s = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))

            .map(Integer::parseInt)

            .collect(toList());

        int result = Result.nonDivisibleSubset(k, s);

        bufferedWriter.write(String.valueOf(result));

        bufferedWriter.newLine();

        bufferedReader.close();

        bufferedWriter.close();

    }

}