입력으로 숫자와 합계를 포함하는 문자열 str이 제공됩니다. 목표는 합계와 동일한 자릿수를 갖는 str까지의 숫자를 찾는 것입니다.
예를 들어 이해합시다.
예를 들어
입력 - N="110" 합계=5
출력 - 주어진 자릿수 합이 있는 N보다 작거나 같은 숫자의 개수는 다음과 같습니다. 7
설명 - 자릿수의 합이 5인 최대 110개의 숫자는 다음과 같습니다.-
5, 14, 23, 32, 41, 50 및 104.
입력 - N="1000" 합계=3
출력 - 주어진 자릿수 합이 있는 N보다 작거나 같은 숫자의 개수는 다음과 같습니다. 10
설명 - 자릿수의 합이 3인 최대 1000개의 숫자는 다음과 같습니다. -
3, 12, 21, 30, 102, 111, 120, 201, 210 및 300.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근 방식에서 우리는 배열 arr[18][2][162]에 숫자와 숫자의 합을 저장하기 위해 동적 프로그래밍을 사용할 것입니다. 여기서 18은 최대 18자리 숫자이고, 2는 값 0과 1입니다. 그리고 162는 18자리가 모두 9( 18*9=162 )인 경우 가능한 최대 합입니다.
요소 arr[i][j][k]의 값은 첫 번째 i자리가 고려되고 j가 0 또는 1인 숫자의 개수를 나타냅니다. N. (N이 123이고 i가 2이면 2자리 숫자가 12보다 크거나 같은지 확인합니다. 12와 같으면 j는 1이 되고 그렇지 않으면 j는 arr[i][j][k에서 0이 됩니다. ] ). 인덱스 k는 arr[i][j][k]에 있는 i자리의 합입니다.
i=N의 숫자이고 k=입력 합계인 경우 결과는 1이고 그렇지 않으면 0입니다.
다음 숫자( i+1th )를 채우기 위해 j를 확인합니다. j가 1이면 i-1 자리는 N의 i-1 자리와 같으므로 다음 자리는 N의 0에서 i+1번째 자리 사이의 값만 가질 수 있으므로 <=N이 됩니다.
j가 0이면 i-1 자리 숫자는 N의 i-1 자리 숫자보다 작습니다. 따라서 다음 숫자(i+1 번째) 위치에 대해 0에서 9 사이의 값을 배치할 수 있으며 여전히 다음보다 작습니다. 아니오.
마지막에 결과를 최종 카운트로 반환합니다.
- 숫자 N과 합계를 숫자의 합으로 나타내는 문자열 str을 사용합니다.
- 배열 arr[18][2][162]를 가져와 memset을 사용하여 -1로 초기화합니다.
- 함수 count_digits(int i, bool check, int temp, int total, string str, int size)는 arr[][][]를 재귀적으로 채우고 끝에 N보다 작거나 같은 숫자의 개수를 주어진 값으로 반환합니다. 숫자 합계.
- 현재 자릿수 i가 N의 자릿수와 같고 현재 합계 온도가 입력 합계와 같으면 1을 반환하고 그렇지 않으면 0을 반환합니다.
- 계산 =arr[i][check][temp]. -1이 아니면 count를 결과로 반환합니다.
- 임시 변수 check_2( bool ) 및 temp_2를 사용합니다. (int).
- for 루프를 사용하여 숫자 0에서 9까지 탐색하고 검사가 1인지 0인지 비교합니다. 1이면 현재 숫자 ch를 str[i]와 비교합니다. 더 크면 루프를 끊습니다(아무것도 하지 않음).
- check_2 설정 =확인 || 채널
- temp_2 =temp + (ch - '0')을 현재 합계로 설정합니다.
- 재귀적으로 자릿수 합계를 계산하기 위해 count_digits(i + 1, check_2, temp_2, total, str, size)를 추가합니다.
- 끝에 결과로 계산됩니다.
예시
#include <bits/stdc++.h>
using namespace std;
int arr[18][2][162];
int count_digits(int i, bool check, int temp, int total, ing str, int size) {
if (i == size) {
if (temp == total) {
return 1;
} else {
return 0;
}
}
int count = arr[i][check][temp];
if (count != -1) {
return count;
}
count = 0;
bool check_2;
int temp_2;
for (char ch = '0'; ch <= '9'; ch++) {
if (!check) {
if (ch > str[i]) {
break;
}
}
check_2 = check || ch < str[i];
temp_2 = temp + (ch - '0');
count += count_digits(i + 1, check_2, temp_2, total, str, size);
}
return count;
}
int main() {
string str = "1101";
int size = str.size();
int total = 5;
memset(arr, -1, sizeof(arr));
cout << "Count of numbers smaller than or equal to N with given digit sum are: " << count_digits(0, 0, 0, total, str, size);
return 0;
} 위의 코드를 실행하면 다음 출력이 생성됩니다 -
출력
Count of numbers smaller than or equal to N with given digit sum are: 26