Chúng ta được cho một số N và một số khác L. Mục đích là tìm các số từ 1 đến N có hiệu giữa chính số đó và tổng các chữ số của nó không nhỏ hơn L.
Nếu N =23, L =10 thì tổng số các số đó sẽ là 4.
23- (2 + 3) =18, 22- (2 + 2) =18, 21- (2 + 1) =18, 20- (2 + 0) =18.
Tất cả các số trên đều thỏa mãn điều kiện
Nhưng 19- (1 + 9) =9 nhỏ hơn L, tương tự là 18,17… .1.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - N =30 L =19
Đầu ra - Đếm số sao cho hiệu số giữa số và tổng các chữ số của nó không nhỏ hơn L là - 1
Giải thích - Chỉ 30 đáp ứng điều kiện, 30- (3 + 0) =27> 19
Đầu vào - N =123330 L =5466
Đầu ra - Đếm số sao cho hiệu số giữa số và tổng các chữ số của nó không nhỏ hơn L là - 6841
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Sử dụng tìm kiếm nhị phân, chúng ta sẽ tìm thấy số đầu tiên đáp ứng điều kiện. Nếu số đó là num thì điều kiện cũng sẽ đúng với num + 1, v.v.
Nếu bất kỳ giá trị giữa nào hiện tại thỏa mãn điều kiện thì tất cả các số từ giữa đến cuối cũng sẽ thỏa mãn điều kiện này, vì vậy chúng ta có thể chỉ cần thêm vào cuối + 1 để đếm.
-
Lấy num và L làm biến dài.
-
Hàm Digit_sum (LL num) nhận một số num và trả về tổng các chữ số của nó.
-
Lấy tổng ban đầu là tổng =0.
-
Sử dụng vòng lặp while, thêm số nhắc nhở là% 10 vào tổng số và giảm số xuống 10. Làm điều này cho đến khi num> 0.
-
Trả về tổng số dưới dạng tổng các chữ số của num.
-
Hàm Less_than_L (LL num, LL L) nhận một số num và một số L và trả về số lượng Số sao cho sự khác biệt giữa số và tổng các chữ số của nó không nhỏ hơn L
-
Lấy số lượng ban đầu là 0.
-
Triển khai tìm kiếm nhị phân bằng vòng lặp while bắt đầu =1 và kết thúc =num.
-
Tính số giữa dưới dạng temp =(start + end) / 2.
-
Nếu sự khác biệt giữa tạm thời và tổng các chữ số của tạm thời không nhỏ hơn L thì tất cả các số lớn hơn tạm thời cũng sẽ thỏa mãn điều kiện tương tự.
-
Đếm các số như vậy bao gồm cả tạm thời sẽ là num-temp + 1. Thêm cái này để đếm. Và đặt end =temp-1.
-
Nếu không, hãy đặt start =temp + 1.
-
Ở cuối số lượng tìm kiếm nhị phân sẽ có các số có sự khác biệt giữa chúng và tổng các chữ số không nhỏ hơn L
-
Kết quả là số lượt trả lại.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of Numbers such that difference between the number and sum of its digits not less than L are: 234267