Target pair sum and power calculation
Filed under Accolite
Free read 3 of 3Understand constraints for the pair sum and clarify if the power check handles edge cases like 0 or negative bases.
The question
Given an array of integers and a target sum, find if there exists a pair of elements that add up to the target in O(n) time. Additionally, determine if one integer is an integer power of another in O(1) time.
Constraints
- Array length will be between 2 and 10^5.
- Power check inputs fit within standard 32-bit integer limits.
Examples
- Input
- arr = [10, 15, 3, 7], k = 17
- Output
- True
- Why
- 10 + 7 = 17, which equals the target sum.
Approach
Understand constraints for the pair sum and clarify if the power check handles edge cases like 0 or negative bases.
Check every possible pair for the sum using nested loops O(n^2), and repeatedly divide for the power check.
Use a Hash Set for the pair sum to achieve O(n) time. For power check in O(1), use logarithms or precomputed bounds since numbers are constrained to standard integer types.
Handle duplicate elements, negative numbers, and numbers equal to 0 or 1.
Solution
O(n) time, O(n) space
def has_pair_with_sum(arr, target):
seen = set()
for num in arr:
if target - num in seen:
return True
seen.add(num)
return False
def is_power(a, b):
if a <= 0 or b <= 0:
return False
if a == 1:
return b == 1
import math
val = round(math.log(b, a), 10)
return abs(val - round(val)) < 1e-9 and a**round(val) == b
Tips
- What they are testing: Test with edge cases such as negative numbers, zero, and base/exponent edge cases like 1 and 0 for powers.
- Common mistake: Using nested loops for the pair sum resulting in O(n^2) time, or using loops/recursion for the power check instead of mathematical properties or bit manipulation.
Related Accolite questions
Collected from public candidate posts and coding forums. Updated Nov 2026.