코인 변경 문제

난이도 중급
자주 묻는 질문 아마존 Apple BlackRock 블룸버그 게시물에서 ByteDance 자본 하나 Facebook 골드만 삭스 구글 신탁 월마트 연구소
배열 동적 프로그래밍조회수 87

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

동전 변경 문제 – c1, c2,…, cs (예 : 1,4,7….) 값이 다른 동전이 주어집니다. 양 n이 필요합니다. 이 주어진 동전을 사용하여 양 n을 형성하십시오. 동전은 필요한만큼 사용할 수 있습니다. 이 동전을 사용하여 금액 n을 얻을 수있는 총 방법 수를 찾으십시오.

예를 들어, 금액 n = 3 및 동전 c = {1,2}로 설정하면 가능한 솔루션은 {1,1,1}입니다. 즉, 가치 1의 동전 3 개는 금액 1,2과 {1}, 즉 각각 동전 하나가됩니다. 따라서 출력은 2입니다.

입력 : n = 5 및 c = {1, 2, 3}

출력 : 5

입력 : n = 34 및 c = {1, 2, 10}

출력 : 42

코인 변경 문제에 대한 재귀 적 방법

암호알고리즘

  1. 초기화 a 변수 n 및 사용 가능한 동전 배열 c.
  2. 첫 번째 기본 사례 – n이 1이면 동전 0을 사용하는 것이 유일한 해결책이므로 XNUMX을 반환합니다.
  3. 둘째 – n이 XNUMX보다 작 으면 가능한 솔루션이 없으므로 XNUMX을 반환합니다.
  4. 셋째 – n이 0보다 크지 만 size = 0 인 동전이 없으면 XNUMX을 반환합니다..
  5. 재귀 사례 – 반환 횟수 (마지막 동전 값을 포함한 솔루션의 합) + 개수 (마지막 코인 값을 제외한 솔루션의 합)

시간 복잡성 : O (2n)

공간 복잡성 : O (크기)

코인 변경 문제에 대한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

int coin_count(int arr[], int size, int n){ 
    // If n is 0 then  
    // do not include any coin
    if(n==0) 
        return 1; 
      
    // If n is less than 0   
    // no solution exists 
    if(n<0) 
        return 0; 
  
    // If coins do not exist and n  
    // is greater than 0, 
    // no solution exist 
    if((size<=0)&&(n>=1)) 
        return 0; 

    return coin_count(arr,size-1,n)+coin_count(arr,size,n-arr[size-1]); 
}
int main(){ 
    int c[] = {1, 2, 3};
    int n=5;
    int size = sizeof(c)/sizeof(c[0]); 
    cout<<coin_count(c, size, n);
    return 0; 
}
Output :
5

코인 변경 문제에 대한 Java 프로그램

import java.io.*; 
class Coins{ 
    static int coin_count(int arr[], int size, int n){ 
        // If n is 0 then  
        // do not include any coin
        if(n==0) 
            return 1; 
          
        // If n is less than 0   
        // no solution exists 
        if(n<0) 
            return 0; 
      
        // If coins do not exist and n  
        // is greater than 0, 
        // no solution exist 
        if((size<=0)&&(n>=1)) 
            return 0; 
    
        return coin_count(arr,size-1,n)+coin_count(arr,size,n-arr[size-1]); 
    }
    public static void main(String[] args){ 
        int c[]={1, 2, 3}; 
        int n=5;
        int size=c.length; 
        System.out.println(coin_count(c, size, n)); 
    } 
}
Output : 
5

 

위 코드의 재귀 트리

코인 변경 문제

위의 트리에서 일부 함수가 두 번 이상 호출되는 것을 볼 수 있습니다. 이것은 ... 불리운다 겹치는 하위 문제 속성.

동적 프로그래밍 방법

위에서 설명한 것과 동일한 문제의 재 계산을 방지하기 위해 어레이는 상향식 방식으로 구성됩니다.

암호알고리즘

  1. 변수 n과 사용 가능한 동전 배열 c를 초기화합니다.
  2. n이 1이면 배열 개수에 0을 저장합니다. 유일한 해결책은 동전 XNUMX 개를 사용하는 것입니다.
  3. 모든 코인 값을 하나씩 탐색하고 선택한 코인의 값보다 크거나 같은 인덱스 뒤의 카운트 배열 값을 업데이트합니다.
  4. 반환 횟수 [n].

시간 복잡성 : O (백만)

공간 복잡성 : O (N)

코인 변경 문제에 대한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

int coin_count(int arr[], int m, int n){ 
    int count[n+1]; 
  
    // Initialise all count values as 0 
    memset(count, 0, sizeof(count)); 

    //if n=0
    count[0] = 1; 

    // update the count[] 
    // values after the index >=
    // the value of the picked coin 
    for (int i=0; i<m; i++) 
        for (int j=arr[i]; j<=n; j++) 
            count[j] += count[j-arr[i]]; 

    return count[n]; 
}  
int main(){ 
    int c[] = {1, 2, 3};
    int n=5;
    int size = sizeof(c)/sizeof(c[0]); 
    cout<<coin_count(c, size, n);
    return 0; 
}
Output : 
5

코인 변경 문제에 대한 Java 프로그램

import java.util.Arrays; 
  
class Coins{ 
    static long coin_count(int arr[], int m, int n){ 
        long[] count = new long[n+1]; 
        
        //Initialise all values of count as 0
        Arrays.fill(count, 0); 
  
        //if n=0
        count[0] = 1; 
  
        // update the count[] 
        // values after the index >=
        // the value of the picked coin 
        for (int i=0; i<m; i++) 
            for (int j=arr[i]; j<=n; j++) 
                count[j] += count[j-arr[i]]; 
  
        return count[n]; 
    } 
    public static void main(String args[]){ 
        int c[] = {1, 2, 3}; 
        int size = c.length; 
        int n = 5; 
        System.out.println(coin_count(c, size, n)); 
    } 
}
Output : 
5

참고  면접 질문

균열 시스템 설계 인터뷰
Translate »