우리는 숫자 N과 다른 숫자 L이 주어집니다. 목표는 숫자 자체와 그 자릿수의 합이 L보다 작지 않은 1과 N 사이의 숫자를 찾는 것입니다.
N=23, L=10이면 이러한 숫자의 개수는 4가 됩니다.
23-(2+3)=18, 22-(2+2)=18, 21-(2+1)=18, 20-(2+0)=18.
위의 모든 숫자는 조건을 충족합니다.
그러나 19-(1+9)=9는 L보다 작으며 마찬가지로 18,17….1.
예를 들어 이해하자
입력 − N=30 L=19
출력 − L보다 작지 않은 숫자와 자릿수의 합이 − 1이 되도록 하는 숫자의 개수
설명 − 30개만 조건을 충족합니다. 30-(3+0)=27> 19
입력 − N=123330 L=5466
출력 − L보다 작지 않은 숫자의 합과 숫자의 차이가 − 6841인 숫자의 개수
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이진 검색을 사용하여 조건을 충족하는 첫 번째 숫자를 찾습니다. 해당 숫자가 num이면 num+1 등에 대해서도 조건이 참이 됩니다.
현재 mid 값이 조건을 충족하면 mid와 end 사이의 모든 숫자도 이 조건을 충족하므로 단순히 end-mid+1을 추가하여 계산할 수 있습니다.
-
num과 L을 long 변수로 사용합니다.
-
함수 Digit_sum(LL num)은 숫자 num을 받아 숫자의 합을 반환합니다.
-
초기 합계를 total=0으로 취합니다.
-
while 루프를 사용하여 알림 num%10을 합계에 추가하고 num을 10만큼 줄입니다. num>0이 될 때까지 이 작업을 수행합니다.
-
num의 자릿수의 합계로 합계를 반환합니다.
-
함수 Less_than_L(LL num, LL L)은 숫자 num과 숫자 L을 취해 숫자와 숫자의 합이 L보다 작지 않도록 숫자의 개수를 반환합니다.
-
초기 카운트를 0으로 합니다.
-
start=1 및 end=num인 while 루프를 사용하여 이진 검색을 구현합니다.
-
중간 숫자를 temp=(start+end)/2로 계산합니다.
-
temp와 temp의 자릿수의 합이 L보다 작지 않으면 temp보다 큰 모든 숫자도 동일한 조건을 만족합니다.
-
temp를 포함한 숫자의 개수는 num-temp+1이 됩니다. 이것을 추가하여 계산합니다. 그리고 end=temp-1을 설정합니다.
-
그렇지 않으면 start=temp+1로 설정하십시오.
-
이진 검색의 끝에서 카운트는 그들 사이의 차이와 L 이상의 자릿수 합을 가진 숫자를 갖습니다.
-
결과로 카운트를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int Digit_sum(LL num){
LL total = 0;
while (num > 0){
total += num % 10;
num = num/10;
z}
return total;
}
LL Less_than_L(LL num, LL L){
LL count = 0;
LL start = 1;
LL end = num;
while (start <= end){
LL temp = (end + start) / 2;
LL temp_2 = temp - Digit_sum(temp);
if (temp_2 >= L){
count = num - temp + 1;
end = temp - 1;
}
else{
start = temp + 1;
}
}
return count;
}
int main(){
LL num = 234516;
LL L = 235;
cout<<"Count of Numbers such that difference between the number and sum of its digits not
less than L are: "<< Less_than_L(num, L);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of Numbers such that difference between the number and sum of its digits not less than L are: 234267