กำหนดสตริง str ที่มีตัวเลขและผลรวม total เป็นอินพุต เป้าหมายคือหาตัวเลขจนถึง str ที่มีผลรวมของหลักเท่ากับ total
ทำความเข้าใจด้วยตัวอย่าง
ตัวอย่าง
Input - N = "110" sum = 5
Output - จำนวนตัวเลขน้อยกว่าหรือเท่ากับ N ที่มีผลรวมหลักกำหนดคือ: 7
คำอธิบาย - ตัวเลขจนถึง 110 ที่มีผลรวมของหลักเท่ากับ 5 คือ:
5, 14, 23, 32, 41, 50 และ 104
Input - N = "1000" sum = 3
Output - จำนวนตัวเลขน้อยกว่าหรือเท่ากับ N ที่มีผลรวมหลักกำหนดคือ: 10
คำอธิบาย - ตัวเลขจนถึง 1000 ที่มีผลรวมของหลักเท่ากับ 3 คือ:
3, 12, 21, 30, 102, 111, 120, 201, 210 และ 300
แนวทางที่ใช้ในโปรแกรมด้านล่าง
ในแนวทางนี้ เราจะใช้ dynamic programming เพื่อเก็บผลรวมของตัวเลขและหลักของพวกเขาในอาร์เรย์ arr[18][2][162] โดย 18 สำหรับตัวเลขสูงสุด 18 หลัก 2 สำหรับค่า 0 และ 1 และ 162 สำหรับผลรวมสูงสุดที่เป็นไปได้ถ้าหลักทั้ง 18 เป็น 9 (18*9 = 162)
ค่าของสมาชิก arr[i][j][k] แสดงจำนวนตัวเลขที่หลักแรก i หลักถูกพิจารณา และ j เป็น 0 หรือ 1 ขึ้นอยู่กับว่าตัวเลขที่สร้างขึ้น i หลักปัจจุบันน้อยกว่าหรือมากกว่าหลักแรก i ของ N (ถ้า N คือ 123 และ i คือ 2 เราจะตรวจสอบว่าตัวเลข 2 หลักเท่ากับหรือมากกว่า 12 หรือไม่ ถ้าเท่ากับ 12 แล้ว j จะเป็น 1 มิฉะนั้น j จะเป็น 0 ใน arr[i][j][k]) ดัชนี k จะเป็นผลรวมของ i หลักใน arr[i][j][k]
ถ้า i = หลักของ N และ k = ผลรวมอินพุต ผลลัพธ์จะเป็น 1 มิฉะนั้น 0
สำหรับการเติมหลักถัดไป (i+1) เราจะตรวจสอบ j ถ้า j เป็น 1 แล้ว i-1 หลักเท่ากับ i-1 หลักของ N ดังนั้นหลักถัดไปสามารถมีค่าระหว่าง 0 ถึง i+1 ของ N เท่านั้นเพื่อให้ <= N
ถ้า j เป็น 0 แล้ว i-1 หลักน้อยกว่า i-1 หลักใน N ดังนั้นเราสามารถวางค่าใดก็ได้ระหว่าง 0 ถึง 9 สำหรับตำแหน่ง i+1 และยังคงน้อยกว่า N
ในที่สุดคืนค่าผลลัพธ์เป็นจำนวนนับสุดท้าย
- รับสตริง str แทนตัวเลข N และ total เป็นผลรวมของหลัก
- รับอาร์เรย์ arr[18][2][162] และเริ่มต้นด้วย -1 ด้วย memset
- ฟังก์ชัน count_digits(int i, bool check, int temp, int total, string str, int size) เรียกซ้ำเติม arr[][][] และในที่สุดคืนค่าจำนวนตัวเลขน้อยกว่าหรือเท่ากับ N ที่มีผลรวมหลักกำหนด
- ถ้าจำนวนหลักปัจจุบัน i เท่ากับหลักของ N และผลรวมปัจจุบัน temp เท่ากับ total อินพุต คืนค่า 1 มิฉะนั้น 0
- รับ count = arr[i][check][temp] ถ้าไม่ใช่ -1 คืนค่า count เป็นผลลัพธ์
- รับตัวแปรชั่วคราว check_2 (bool) และ temp_2 (int)
- วนลูปหลัก 0 ถึง 9 ด้วย for loop และเปรียบเทียบถ้า check เป็น 1 หรือ 0 ถ้า 1 เปรียบเทียบหลักปัจจุบัน ch กับ str[i] ถ้ามากกว่า break ลูป (ไม่ทำอะไร)
- ตั้ง check_2 = check || ch < str[i]
- ตั้ง temp_2 = temp + (ch - '0') เป็นผลรวมปัจจุบัน
- บวก count_digits(i + 1, check_2, temp_2, total, str, size) เข้า count เพื่อคำนวณผลรวมของหลักแบบเรียกซ้ำ
- ในที่สุดคืนค่า count เป็นผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int arr[18][2][162];
int count_digits(int i, bool check, int temp, int total, string 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
