ตัวเลข N หลักหารด้วย 5 ที่เกิดจากหลัก M ใน C++

เราได้ให้ตัวเลข N พร้อมกับอาร์เรย์ของตัวเลข M งานของเราคือการหาจำนวนตัวเลข n หลัก ที่เกิดขึ้นจากตัวเลข M ที่ให้มาซึ่งหารด้วย 5 ลงตัว

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหาอินพุตและเอาต์พุต

ใน -

N = 2
M = 3
arr = {5, 6, 3}

ออก −

2

มีเลข N สองตัว 35 และ 65 ที่หารด้วย 5 ลงตัว มาดูตัวอย่างอื่นกัน

ป้อนข้อมูล -

N = 1
M = 7
arr = {2, 3, 4, 5, 6, 7, 8}

ผลลัพธ์ −

1

ในอาร์เรย์ที่ระบุมีตัวเลขเพียง 1 ตัวซึ่งมี 1 หลัก หารด้วย 5 ลงตัว ดังนั้นงานของเราคือการหาจำนวนตัวเลขที่สามารถสร้างได้จากตัวเลขที่กำหนดด้วยตัวเลข N ที่หารด้วย 5 ลงตัว

ตัวเลขต้องลงท้ายด้วยตัวเลข 0 หรือ 5 จึงจะหารด้วย 5 ลงตัว มาดูอัลกอริธึมกัน

อัลกอริทึม

• ตรวจสอบ 0 และ 5 ในอาร์เรย์ที่กำหนด 2. ถ้ามีทั้ง 0 และ 5 แล้ว มีสองวิธีที่จะวางหลักในหน่วยวาง มิเช่นนั้นจะมีวิธีวางหลักทางเดียว
  • เริ่มนับถึง 2
  • ตอนนี้ ที่ที่เหลือสามารถมี m - 1, m - 2, m - 3, ... n วิธีเติมตามลำดับ
  • เขียนลูปที่วนซ้ำจาก 0 ถึง n - 1.
    • ลดขนาดของอาร์เรย์นั้น
    • คูณด้วยการนับ
• หากมีเลขตัวเดียว 0 หรือ 5 แสดงว่ามีทางเดียวเท่านั้นที่จะวางหลักในหน่วยที่
  • เริ่มนับถึง 2
  • ตอนนี้ ที่ที่เหลือสามารถมี m - 1, m - 2, m - 3, ... n วิธีเติมตามลำดับ
  • เขียนลูปที่วนซ้ำจาก 0 ถึง n - 1.
    • ลดขนาดของอาร์เรย์นั้น
    • คูณด้วยการนับ
• หากไม่มีตัวเลข 0 หรือ 5 อยู่ เราสามารถสร้างตัวเลขที่หารด้วย 5 ลงตัวได้ ให้คืนค่า -1 ในกรณีนั้น

การนำไปใช้

ต่อไปนี้เป็นการนำอัลกอริธึมข้างต้นไปใช้ใน C++

#include <bits/stdc++.h>

using namespace std;

int numbers(int n, int m, int arr[]) {
   bool isZeroPresent = false, isFivePresent = false;
   int numbersCount = 0;
   if (m < n) {
      return -1;
   }
   for (int i = 0; i < m; i++) {
      if (arr[i] == 0) {
         isZeroPresent = true;
      }
      if (arr[i] == 5) {
         isFivePresent = true;
      }
   }
   if (isZeroPresent && isFivePresent) {
      numbersCount = 2;
      for (int i = 0; i < n - 1; i++) {
         m--;
         numbersCount = numbersCount * m;
      }
   } else if (isZeroPresent || isFivePresent) {
      numbersCount = 1;
      for (int i = 0; i < n - 1; i++) {
         m--;
         numbersCount = numbersCount * m;
      }
   } else {
      return -1;
   }
   return numbersCount;
}
int main() {
   int arr[] = {5, 6, 3};
   cout << numbers(2, 3, arr) << endl;
   return 0;
}

ผลลัพธ์

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

2