นับจำนวนที่สร้างได้จาก N โดยบวก 1 และลบศูนย์นำหน้าด้วย C++

ได้รับจำนวน N เป็นอินพุต ทำสองขั้นตอนกับ N และหาจำนวนตัวเลขที่ไม่ซ้ำกันที่สร้างขึ้น ขั้นตอนคือ:

• บวก 1 เข้ากับตัวเลข
• ลบศูนย์นำหน้าออกจากตัวเลขที่ได้ (ถ้ามี)

ถ้า N=8 ตัวเลขที่ได้จะเป็น:

ขั้นตอน 1: 8 → 9 →

ขั้นตอน 2: 1 → (ลบ 0 จาก 10)

ขั้นตอน 1: 2 → 3 → 4 → 5 → 6 → 7 → 8 (ลำดับเดิมซ้ำ)

จำนวนตัวเลขที่ไม่ซ้ำ = 9

ตัวอย่าง

Input

N=21

Output

Count of unique numbers that can be generated from N by adding one and removing trailing zeros are: 18

Explanation

Numbers will be: 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3 ---now same sequence Unique numbers are: 18

Input

N=38

Output

Count of unique numbers that can be generated from N by adding one and removing trailing zeros are: 11

Explanation

Numbers will be: 38, 39, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4 ---now same sequence Unique numbers are: 11

วิธีการที่ใช้ในโปรแกรม

วิธีนี้สร้าง unordered_set<int> U_S ที่จะเก็บตัวเลขที่ไม่ซ้ำทั้งหมดหลังจากทำขั้นตอน 1 และ 2 ถ้าตัวเลขซ้ำ จะหยุดการวนลูป ขนาดของเซตจะให้จำนวนตัวเลขที่ไม่ซ้ำ

• รับตัวเลข N เป็นจำนวนเต็ม
• สร้าง unordered_set<int> U_S สำหรับใส่ตัวเลขที่ได้
• ฟังก์ชัน unique_N(unordered_set<int>& U_S, int N) ใส่ตัวเลขเข้าเซตจนกว่าจะซ้ำ
• ถ้า U_S.count(N) คืนค่า 1 แสดงว่า N อยู่ในเซตแล้ว ตัวเลขจะซ้ำ คืนค่าจากฟังก์ชัน
• มิฉะนั้น ใส่ N เข้าเซต และทำขั้นตอน 1 (บวก 1)
• ตรวจสอบว่า N มีศูนย์นำหน้าหรือไม่ (เป็นจำนวนเท่าของ 10)
• ถ้า N % 10 == 0 ลบศูนย์นำหน้าด้วยการหาร 10
• เรียก unique_N() อีกครั้งด้วย N ที่อัปเดตแล้ว
• หลังคืนจากฟังก์ชัน นับ count = U_S.size()
• พิมพ์ผลลัพธ์เป็น count

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

void unique_N(unordered_set<int>& U_S, int N){
    if (U_S.count(N)){
        return;
    }
    U_S.insert(N);
    N = N + 1;
    while (N % 10 == 0){
        N = N / 10;
    }
    unique_N(U_S, N);
}

int main(){
    int N = 7;
    unordered_set<int> U_S;
    unique_N(U_S, N);
    int count = U_S.size();
    cout << "Count of unique numbers that can be generated from N by adding one and removing trailing zeros are: " << count;
    return 0;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of unique numbers that can be generated from N by adding one and removing trailing zeros are: 9