ในปัญหานี้ เราได้รับค่า x และ y สองค่า งานของเราคือ หาค่าของ y mod (2 ยกกำลัง x) .
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : x = 2, y = 19 Output : 3
คำอธิบาย −
y % 2x = 19 % 22 = 19 % 4 = 3
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการคำนวณค่า 2 x . โดยตรง โดยใช้ฟังก์ชัน pow() แล้วหาค่าของ y % 2 x .
แนวทางอื่นในการแก้ปัญหาคือการใช้บันทึก สำหรับค่าของ y <2 x , ส่วนที่เหลือคือ y สำหรับกรณีนี้เรามี
บันทึก2 y
นอกจากนี้ ค่าสูงสุดของ x สามารถเท่ากับ 63 ซึ่งจะมีค่าล้นสำหรับ y ดังนั้น mod จึงเท่ากับ x
เมื่อพิจารณาทั้งหมดนี้แล้ว เรามีสามกรณีนี้ -
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเราif(log y < x) -> return y
else if(x > 63) -> return y
else -> return (y % pow(2, x))
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
long long int findModVal(long long int y, int x){
if (log2(y) < x)
return y;
if (x > 63)
return y;
return (y % (1 << x));
}
int main(){
long long int y = 82829;
int x = 12;
cout<<"The value of y mod 2^x is "<<findModVal(y, x);
return 0;
} ผลลัพธ์
The value of y mod 2^x is 909
