นับตัวเลขในช่วงที่ผลต่างระหว่างผลรวมหลักตำแหน่งคู่และคี่เป็นเฉพาะใน C++

กำหนดตัวเลขสองตัว start และ end เป็นตัวแปรช่วง เป้าหมายคือหาจำนวนตัวเลขที่อยู่ในช่วง [start, end] และมีผลต่างของผลรวมหลักตำแหน่งคู่และผลรวมหลักตำแหน่งคี่เป็นจำนวนเฉพาะ

คือ (ผลรวมหลักตำแหน่งคู่) - (ผลรวมหลักตำแหน่งคี่) = จำนวนเฉพาะ

ทำความเข้าใจด้วยตัวอย่าง

ตัวอย่าง

Input - start = 230, end = 270

Output - จำนวนตัวเลขในช่วงที่ผลต่างระหว่างผลรวมหลักตำแหน่งคู่และคี่เป็นเฉพาะคือ: 6

คำอธิบาย - ตัวเลขระหว่าง 230 ถึง 270 ที่ตรงเงื่อนไขคือ:

240 (4-2 = 2), 250 (5-2 = 3), 251 (5-3 = 2), 261 (6-3 = 3), 262 (6-4 = 2), 270 (7-2 = 5)

ผลต่างทั้งหมดคือ 2, 3 และ 5 ซึ่งเป็นจำนวนเฉพาะ

Input - start = 1101, end = 1120

Output - จำนวนตัวเลขในช่วงที่ผลต่างระหว่างผลรวมหลักตำแหน่งคู่และคี่เป็นเฉพาะคือ: 1

คำอธิบาย - ตัวเลขระหว่าง 1101 ถึง 1120 ที่ตรงเงื่อนไขคือ:

1120 (3-1 = 2) 2 เป็นจำนวนเฉพาะ

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

ในนี้เราใช้แนวทาง dynamic programming และเก็บจำนวนตัวเลขที่มีผลต่างเฉพาะของผลรวมหลักตำแหน่งคู่และคี่ อาร์เรย์นี้จะเป็น arr[size][90][90][2] โดย size คือกำลังของ 10 ดังนั้นตัวเลขสูงสุดเป็นอินพุทจะเป็น 10^size

ในแต่ละการเรียกซ้ำฟังก์ชัน check(int place, int eve, int od, int temp, vector<int> vec) เราจะสร้างตัวเลขโดยวางหลัก 0 ถึง 9 จากซ้ายไปขวา

ใน arr[size][x][y][temp], x สำหรับผลรวมหลักตำแหน่งคู่ที่วางจนถึง x และ y สำหรับผลรวมหลักตำแหน่งคี่ที่วางจนถึง y ตรวจสอบว่าผลต่างที่ต้องการเป็นเฉพาะหรือไม่โดยใช้อาร์เรย์ arr_2[] ที่เก็บจำนวนเฉพาะทั้งหมดจนถึง 100 ตามลำดับ

• รับตัวแปร start และ end เป็นอินพุต
• รับอาร์เรย์ global arr[size][90][90][2] และอาร์เรย์ arr_2[] สำหรับจำนวนเฉพาะถึง 100
• ฟังก์ชัน check(int place, int eve, int od, int temp, vector<int> vec) รับตำแหน่งหลักปัจจุบันเป็น place, ผลรวมหลักตำแหน่งคู่ปัจจุบันเป็น even และตำแหน่งคี่เป็น od, ค่า temp และ vector vec ที่มีหลัก
• มันเติมค่าที่ arr[place][eve][od][temp] แบบเรียกซ้ำ
• รับค่าเริ่มต้นสำหรับสมาชิกปัจจุบันเป็น count = 0
• สำหรับตำแหน่งปัจจุบัน ตรวจสอบว่าตำแหน่งเป็นตำแหน่งสุดท้ายหรือไม่ด้วย if(place == vec.size()) ถ้าใช่ ตรวจสอบว่าตำแหน่งนั้นคู่หรือคี่
• if(vec.size() & 1) ให้ true แล้วตำแหน่งปัจจุบันเป็นคี่ สลับ eve กับ od เพราะเป็นตัวเลขความยาวคี่
• คำนวณ temp_2 เป็นผลต่างของผลรวมเป็น eve - od
• ใช้ for loop เดินทางผ่าน arr_2[] และตรวจสอบว่า temp_2 พบหรือไม่ ถ้าใช่มันเป็นเฉพาะ คืนค่า 1 มิฉะนั้น 0
• ถ้า arr[place][eve][od][temp] คำนวณแล้ว จะไม่ใช่ -1 คืนค่ามัน
• ถ้า temp ไม่เป็นศูนย์ ตั้ง temp_3 = 9 temp_3 คือขีดจำกัดสูงสุดของหลักที่เราสามารถวางได้ ถ้าเป็น 0 วาง vec[place] มิฉะนั้นตัวเลขน้อยกว่าแล้ว วางหลักใดก็ได้เช่น 9
• วนลูปหลักจาก 0 ถึง temp_3 ถ้าตำแหน่งปัจจุบันเป็นคี่ อัปเดต set_odd = set_odd + i (ผลรวมตำแหน่งคี่ก่อนหน้า + หลักปัจจุบัน i)
• ถ้าตำแหน่งปัจจุบันเป็นคู่ อัปเดต set_even = set_even + i (ผลรวมตำแหน่งคู่ก่อนหน้า + หลักปัจจุบัน i)
• ตั้ง count += check(place + 1, set_even, set_odd, set_temp, vec) และคืนค่า arr[place][eve][od][temp] = count
• ฟังก์ชัน place_prime(int val) รับตัวเลข val และสร้าง vector vec ที่มีหลักจาก LSB ถึง MSB
• ตั้งอาร์เรย์ arr[][][][] ทั้งหมดเป็น -1
• รับ count = check(0, 0, 0, 0, vec) ซึ่งจะคืนค่าผลลัพธ์ในที่สุด
• คืนค่า count เป็นผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h> 
using namespace std; 
const int size = 18; 
int arr[size][90][90][2]; 
// first 100 prime Numbers 
int arr_2[] = { 
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
    31, 37, 43, 47, 53, 59, 61, 67, 71, 73, 
    79, 83, 89, 97 
}; 

int check(int place, int eve, int od, int temp, vector < int > vec) { 
    int count; 
    int temp_3; 
    if (place == vec.size()) { 
        if (vec.size() & 1) { 
            swap(od, eve); 
        } 
        int temp_2 = eve - od; 
        for (int i = 0; i < 24; i++) { 
            if (temp_2 == arr_2[i]) { 
                return 1; 
            } 
        } 
        return 0; 
    } 
    if (arr[place][eve][od][temp] != -1) { 
        int set = arr[place][eve][od][temp]; 
        return set; 
    } 
    if (temp) { 
        temp_3 = 9; 
    } else { 
        temp_3 = vec[place]; 
    } 
    for (int i = 0; i <= temp_3; i++) { 
        int set_temp = temp; 
        int set_even = eve; 
        int set_odd = od; 
        if (i < vec[place]) { 
            set_temp = 1; 
        } 
        if (place & 1) { 
            set_odd = set_odd + i; 
        } else { 
            set_even = set_even + i; 
        } 
        count += check(place + 1, set_even, set_odd, set_temp, vec); 
    } 
    return arr[place][eve][od][temp] = count; 
} 

int place_prime(int val) { 
    vector < int > vec; 
    while (val) { 
        vec.push_back(val % 10); 
        val = val / 10; 
    } 
    reverse(vec.begin(), vec.end()); 
    memset(arr, -1, sizeof(arr)); 
    int count = check(0, 0, 0, 0, vec); 
    return count; 
} 

int main() { 
    int start = 20, end = 80; 
    int count = place_prime(end) - place_prime(start - 1); 
    cout << "Count of Numbers in Range with difference between Sum of digits at even and odd positions as Prime are: " << count; 
    return 0; 
}

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

ผลลัพธ์

Count of Numbers in Range with difference between Sum of digits at even and odd positions as Prime are: 15