นับจำนวนเฉพาะที่สามารถสร้างจาก N โดยการเพิ่มหนึ่งและลบศูนย์ต่อท้ายใน C++

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

• เพิ่ม 1 ให้กับตัวเลข

• ลบเลขศูนย์ต่อท้ายออกจากตัวเลขที่สร้างขึ้น หากมี

ถ้า N คือ 8 ตัวเลขที่สร้างจะเป็น

ใช้ขั้นตอนที่ 1− 8 → 9 →

ใช้ขั้นตอนที่ 2− 1 → ( ลบ 0 จาก 10 )

ใช้ขั้นตอนที่ 1:2 → 3 → 4 → 5 → 6 → 7 → 8 ( ลำดับเดียวกัน )

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

ตัวอย่าง

อินพุต

N=21

ผลลัพธ์

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

คำอธิบาย

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

อินพุต

N=38

ผลลัพธ์

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

คำอธิบาย

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

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

ในแนวทางนี้ เราจะสร้างชุดที่ไม่เรียงลำดับซึ่งจะมีตัวเลขเฉพาะทั้งหมดที่สร้างขึ้นหลังจากใช้ขั้นตอนที่ 1 และ 2 ในกรณีที่ตัวเลขซ้ำ เราจะหยุดการทำซ้ำ ขนาดของชุดจะทำให้เรานับจำนวนเฉพาะที่สร้างขึ้นในกระบวนการ

• นำตัวเลข N เป็นจำนวนเต็ม

• ใช้ unordered_set U_S เพื่อใส่ตัวเลขที่สร้างขึ้น

• ฟังก์ชัน unique_N(unordered_set&U_S, int N) รับเซตและ N และเพิ่มตัวเลขไปยังชุด U_S จนกว่าตัวเลขทั้งหมดจะไม่ซ้ำกันในนั้น

• หาก U_S.count(N) คืนค่า 1 แสดงว่ามี N อยู่ในชุดแล้ว ดังนั้นตัวเลขจะซ้ำกัน กลับจากฟังก์ชัน

• มิฉะนั้นให้ใส่ N ลงในชุดและใช้การดำเนินการ 1 ( เพิ่มขึ้นทีละ 1)

• ตรวจสอบว่าหมายเลข N มีศูนย์ต่อท้ายหรือไม่ (ผลคูณของ 10)

• หาก N % 10 เป็น 0 ให้ลบศูนย์ต่อท้ายด้วยการหารด้วย 10

• เรียกใช้ฟังก์ชัน unique_N() พร้อมอัปเดต N.

• หลังจากกลับจากฟังก์ชัน ให้นับเป็นขนาดของชุด U_S

• พิมพ์ผลลัพธ์ตามจำนวน

ตัวอย่าง

#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;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

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