ลดอาร์เรย์ให้เหลืออิลิเมนต์เดียวด้วยการดำเนินการที่กำหนดใน C++

ภาพรวม

ได้รับตัวแปรจำนวนเต็ม Number เป็นอินพุต พิจารณาอาร์เรย์ที่มีอิลิเมนต์ 1 ถึง Number เรียงลำดับจากน้อยไปมาก หากดำเนินการโดยที่แต่ละขั้นตอนจะนำอิลิเมนต์ที่อยู่ตำแหน่งคี่ (Odd positions) ออก จะได้อาร์เรย์ใหม่ ทำซ้ำจนเหลืออิลิเมนต์เพียงตัวเดียว พิมพ์ตัวเลขตัวนั้น

หมายเหตุ: ตำแหน่งเริ่มจาก 1 คือดัชนี 0 ตำแหน่ง 2 คือดัชนี 1 ตามลำดับ

กรณีทดสอบ

Number=1 → output=1

Number=2 → output=2

Number=3 → output=2

Number=4 → output=4

Number=5 → output=4

Number=6 → output=4

Number=7 → output=4

...

Number=12 → output=8

Number=20 → output=16

สังเกตได้ว่า: สำหรับช่วง 2ⁱ ถึง 2ⁱ⁺¹-1 ผลลัพธ์จะเป็น 2ⁱ

ตัวอย่าง

อินพุต − Number = 7

เอาต์พุต − The single element after reduction operation is: 4

คำอธิบาย − อาร์เรย์ [1 2 3 4 5 6 7]

หลังครั้งที่ 1: [2 4 6]

หลังครั้งที่ 2: [4]

อินพุต − Number = 18

เอาต์พุต − The single element after reduction operation is: 16

คำอธิบาย − อาร์เรย์ [1..18]

ครั้งที่ 1: [2 4 6 8 10 12 14 16 18]

ครั้งที่ 2: [2 8 12 16]

ครั้งที่ 3: [8 16]

ครั้งที่ 4: [16]

แนวทางการแก้ปัญหา

ใช้ while loop คำนวณผลลัพธ์จากสูตรข้างต้น เริ่มต้นค่า 2 วนลูปจนกว่า 2*result > Number คูณ 2 ทุกครั้ง

• รับตัวแปร Number
• ฟังก์ชัน getsingleElement(long num) พิมพ์ผลลัพธ์ตามสูตร
• ตัวแปร result เริ่มต้น = 2
• while result*2 <= num คูณ result ด้วย 2
• คืนค่า result
• พิมพ์ใน main

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

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

long getsingleElement(long num){ 
    long result; 
    result = 2; 
    while(result * 2 <= num){ 
        result = result * 2; 
    } 
    return result; 
} 

int main(){ 
    int Number = 20; 
    cout << "The single element after reduction operation is: " << getsingleElement(Number); 
    return 0; 
}

ผลลัพธ์

The single element after reduction operation is: 16