จำนวน N หลักที่หาร 5 ลงตัวสร้างจาก M หลักใน C++

โจทย์

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

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

อินพุต −

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

เอาต์พุต −

 2

มีตัวเลข N หลัก 2 ตัวคือ 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