고유 한 짝수를 갖는 부분 집합 계산


난이도 쉽게
자주 묻는 질문 시스코 Expedia 미트라 SAP 연구소 Taxi4Sure
배열 해시 집합

우리는 모두 인터뷰에서 어느 시점에서 하위 집합 문제로 어려움을 겪었습니다. 면접관들도 이러한 문제를 좋아합니다. 이러한 문제는 학생들의 이해와 사고 과정을 검토하는 데 도움이됩니다. 따라서 더 이상 고민하지 않고 문제로 바로 뛰어들겠습니다.

섹션 1

문제 진술

숫자의 조합 / 배열이 제공되었습니다. 우리는 고유 한 짝수를 가질 수있는 서브 세트의 수를 등록해야합니다.

작은 예를 들어 보겠습니다.

입력:

[1,2,5,6,3,2,1,1,8]

가능한 하위 집합 :

[2,6]

[6,8]

[2,6,8]

참고 : 동일한 번호를 가진 부분 집합은 다른 것으로 간주되지 않습니다.

가능한 대답 하위 집합 중 하나를 강조 표시하여 동일한 내용을 설명하겠습니다.

고유 한 짝수를 갖는 부분 집합 계산

섹션 2

분석

우리가 원하는 것을 찾을 수있는 다양한 방법이 있습니다. 그만큼 브 루트 포스 하나는 가능한 모든 하위 집합을 찾은 다음 규칙을 충족하는 하위 집합을 찾는 것입니다.

위의 방법은 머리를 벽에 두드리는 것 이상입니다. 따라서 어리석은 소리로 들리는 당혹감을 덜기 위해 가능한 가장 좋은 시간에 답을 얻을 수있는 가장 쉬운 방법을 찾았습니다.

우리는 짝수를 만날 때마다 두 가지 선택이 있습니다

  • 하위 집합에 포함되도록 선택할 수 있습니다.
  • 하위 집합에서 제외되도록 선택할 수 있습니다.

따라서 현재 우리가 가진 유일한 임무는 숫자가 고유한지 여부를 결정하는 것입니다. (앞서 언급 한 규칙 덕분에)

프로세스를 XNUMX으로 설정하겠습니다.

  • 첫째, HashSet 우리가 만난 짝수를 저장하기 위해
  • 둘째, 루프 실행
  • 숫자가 짝수인지 확인
  • 숫자가 짝수이면 HashSet에 추가합니다.
  • HashSet에는 고유 한 요소 만 들어오는 것을 보장하는 자체 순서가 있습니다.
  • 그런 다음 HashSet에서 요소 수를 찾습니다.
  • 이 수는 우리가 가진 고유 한 짝수 수를 나타냅니다.
  • 이 개수를 사용하여 하위 집합의 수를 찾을 수 있습니다.
  • 부분 집합 개수 = 2 ^ count-1

위의 프로세스는 다음과 같이 코드에 넣을 수 있습니다.

고유 한 짝수를 갖는 개수 하위 집합에 대한 Java 코드

public class Main
{
    public static int evenSub(int arr[],int n)
    {
        HashSet<Integer>store=new HashSet<Integer>();
        for(int i=0;i<arr.length;i++)
        {
            if(arr[i]%2==0)
                store.add(arr[i]);
        }
        int p=store.size();
        return (int)(Math.pow(2,p)-1);
    }
    public static void main(String[] args)  
    { 
    int arr[] = {2, 1, 9, 2, 6, 5, 3}; 
    int n = arr.length; 
    System.out.println
        ("Number of subsets = "+ evenSub(arr, n)); 
    }
}
2, 1, 9, 2, 6, 5, 3
3

고유 한 짝수를 갖는 개수 하위 집합에 대한 C ++ 코드

Java에서 C ++로 전환 할 때 HashSet 대신 Unordered Set를 사용하고 몇 가지 매개 변수를 사용하여 우리에게 적합합니다.

int evenSub(int arr[],int n)
{
    unordered_set<int>store; 
    for(int i=0;i<n;i++)
    {
        if(arr[i]%2==0)
            store.insert(arr[i]);
    }
    int p=store.size();
    return (pow(2,p)-1);
}
int main() 
{
    int arr[] = {
4, 2, 1, 9, 2, 6, 5, 3
7

고유 한 짝수를 갖는 개수 하위 집합에 대한 복잡성 분석

시간 복잡성 = O (n)

공간 복잡성 = O (n)

시간 복잡성

  • 배열을 통과 할 때 O (n)입니다.
  • 하위 집합에 추가하기 전에 모든 요소를 ​​살펴 봅니다.

공간 복잡성

  • 최악의 경우 전체 배열을 저장하게 될 수 있으므로 O (n)입니다.