ที่นี่เราจะเห็นปัญหาที่น่าสนใจอย่างหนึ่ง เราจะพบคู่ (x, y) โดยที่ x และ y อยู่ในช่วง ดังนั้น l <=x, y <=r ทั้งคู่จะมีหนึ่งคุณสมบัติ ค่าของ x หารด้วย y . หากมีหลายคู่ให้เลือกเพียงคู่เดียว
เราสามารถแก้ปัญหานี้ได้ในเวลา O(1) หากเราได้ค่าขีดจำกัดล่าง l และ 2l เรารู้ว่าค่าที่น้อยที่สุดของ y/x สามารถเป็น 2 และหากมีค่าที่มากกว่าอยู่ในช่วงนั้น 2 จะอยู่ในช่วง และถ้าเราเพิ่ม x ก็จะเพิ่มขึ้น 2 เท่าด้วย ดังนั้น l และ 2l จะเป็นคู่ขั้นต่ำที่จะตกอยู่ในช่วงที่กำหนด
ตัวอย่าง
#include<iostream>
using namespace std;
void getPair(int l, int r) {
int x = l;
int y = 2 * l;
cout << "(" << x << ", " << y << ")" << endl;
}
int main() {
int l = 3, r = 6;
getPair(l, r);
} ผลลัพธ์
(3, 6)
