PracticeAlgorithms

Find a Safe Pair of Log Token IDs

BeginnerAlgorithmscomparisonboundary handlinginvariants Time not estimated Not started

Context

A document-processing service assigns consecutive integer IDs to tokens in a diagnostic log. Given the smallest and largest allowed IDs, find two different IDs whose least common multiple is also an allowed ID. The service needs a direct construction rather than a search through all token-ID pairs.

Problem

Given an inclusive interval from lower_id to upper_id, return two distinct integers from that interval whose least common multiple is within the same interval. If such a pair cannot exist, return an empty list.

Use the constant-time construction based on the lower endpoint and its double. When the double is no greater than the upper endpoint, return [lower_id, 2 * lower_id]. Otherwise, return []. The endpoints are inclusive, and the returned pair must be ordered from smaller to larger value.

Examples

Example 1

Input: lower_id = 3upper_id = 8

Output: [3, 6]

Explanation: For the interval from 3 to 8, the executed output is [3, 6].

Example 2

Input: lower_id = 7upper_id = 10

Output: []

Explanation: For the interval from 7 to 10, the executed output is [].

Example 3

Input: lower_id = 5upper_id = 10

Output: [5, 10]

Explanation: For the interval from 5 to 10, the executed output is [5, 10].

Constraints

1 <= lower_id <= 1000000000
lower_id <= upper_id <= 2000000000
Types: lower_id is int, upper_id is int; result is int[]

Function signature

def find_log_token_pair(lower_id: int, upper_id: int) -> list[int]

lower_id int: The smallest allowed token ID.
upper_id int: The largest allowed token ID.
returns list[int]: The constructed pair in increasing order, or an empty list when the interval cannot contain a valid pair.

Adapted from MBPP problem task_177 (CC BY 4.0). Rewritten, extended and verified by Iksha.

Notes

An empty list is the designated failure result.
The least common multiple of n and 2n is 2n for every positive n.

Code

Saved

Checking environment…Python SandboxLn 1, Col 1

lower_id =upper_id =