변수에서 시작하여 변수 끝까지, 변수 k와 d까지 정수 범위가 주어집니다. 작업은 d가 정확히 k번 발생하도록 범위에서 자릿수 d의 개수를 계산하는 것입니다.
예
입력 - int 시작 =10, int 끝 =100, d =4 및 K =2
출력 - 숫자 d가 정확히 K번 발생하는 범위의 숫자 개수:1
설명 - 범위는 10에서 100까지입니다. 따라서 숫자 d, 즉 4가 있는 가능한 숫자는 정확히 k 발생합니다. 즉 2번은 44이므로 개수는 1입니다.
입력 - int 시작 =10, 끝 =100, d =6 및 m =1
출력 - 숫자 d가 정확히 K번 발생하는 범위의 숫자 개수:1
설명 - 범위는 10에서 100까지입니다. 따라서 숫자 d 즉 4가 있는 가능한 숫자는 정확히 k 발생합니다. 즉 1번은 16, 26, 36, 46, 56, 76, 86 및 96이므로 개수는 8입니다. 6은 k번 이상 발생하므로 66을 고려하지 마십시오.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
- 변수 시작부터 변수 끝까지 정수 범위를 만들고 변수 d와 k를 선언하고 값을 입력합니다. 추가 처리를 위해 데이터를 함수에 전달합니다.
- vec라고 가정해 봅시다. 벡터 유형의 변수를 생성합니다.
- 변수 start 내부의 값이 될 때까지 루프를 시작합니다. 이제 while 내부에서 값을 val % 10으로 벡터에 푸시하고 val을 val / 10으로 설정합니다.
- vec.begin() 및 vec.end()를 인수로 전달하여 STL에서 역함수를 호출합니다.
- memset을 사용하여 배열의 값을 -1로 설정합니다.
- 짝수 위치에 있는 숫자가 m으로 나누어 떨어지는지 확인하는 함수인 set_total(0, 0, 0, vec) 반환
- set_total 함수 내부-:
- IF place가 벡터의 크기인지 확인한 다음 IF temp =k를 확인한 다음 1을 반환하거나 0을 반환합니다.
- IF arr[place][temp][val][rem]이 -1과 같지 않은지 확인한 다음 arr[place][temp][val][rem]의 값을 반환합니다.
- 결과를 저장할 변수 개수를 선언합니다.
- 변수 temp_2를 선언하고 9로 설정합니다. IF val은 1과 같음 ELSE는 vec[place]로 설정합니다.
- i에서 0까지 FOR 루프를 시작하고 temp_2까지 IF i가 d인지 확인한 다음 IF d note가 0이거나 d가 0이고 rem =1인지 확인한 다음 합계를 1씩 증가시킵니다.
- 변수를 temp_2로 선언하고 val로 설정
- vec[place]보다 작은지 확인한 다음 temp_2를 1로 설정
- set_total 함수에 대한 재귀 호출로 개수 설정
- arr[place][temp][val] =count를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
const int MAX = 20;
int arr[MAX][MAX][2][2];
int d, K;
int set_total(int place, int temp, int val, int rem, vector < int > vec) {
if (place == vec.size()) {
if (temp == K) {
return 1;
}
return 0;
}
if (arr[place][temp][val][rem] != -1) {
return arr[place][temp][val][rem];
}
int count = 0;
int temp_2 = (val ? 9 : vec[place]);
for (int i = 0; i <= temp_2; i++) {
int total = temp;
if (i == d) {
if (d != 0 || (!d && rem)) {
total++;
}
}
int total_2 = val;
if (i < vec[place]) {
total_2 = 1;
}
count += set_total(place + 1, total, total_2, rem || (i != 0), vec);
}
return arr[place][temp][val][rem] = count;
}
int occurrence_d(int val) {
vector < int > vec;
while (val) {
vec.push_back(val % 10);
val = val / 10;
}
reverse(vec.begin(), vec.end());
memset(arr, -1, sizeof(arr));
return set_total(0, 0, 0, 0, vec);
}
int main() {
int start = 10;
int end = 100;
d = 4, K = 2;
int count = occurrence_d(end) - occurrence_d(start - 1);
cout << "Count of Numbers in a Range where digit d occurs exactly K times are: " << count;
return 0;
} 위의 코드를 실행하면 다음 출력이 생성됩니다 -
출력
Count of Numbers in a Range where digit d occurs exactly K times are: 1