Divisibility count and Subarray sum
Filed under Amazon
Free read 2 of 3Confirm data types required for large numbers and exact constraints on subarray sums.
The question
Part 1: Count how many integers from 1 up to 10^16 are divisible by integer a or integer b. Part 2: Find the maximum contiguous subarray length or stations covered such that the sum of elements from tribe A does not exceed k.
Constraints
- Numbers up to 10^16, requiring 64-bit integers
- Array elements non-negative
Examples
- Input
- n = 10, a = 2, b = 3
- Output
- 7
- Why
- Numbers up to 10 divisible by 2 or 3 are 2, 3, 4, 6, 8, 9, 10 (total 7).
Approach
Confirm data types required for large numbers and exact constraints on subarray sums.
Iterate up to 10^16 or check all subarrays, which will TLE.
Use inclusion-exclusion principle with GCD/LCM for the divisibility count. Use a sliding window or two pointers for the subarray sum problem.
Values where a and b share common factors; empty subarrays or k smaller than minimum element.
Tips
- What they are testing: Test with large values near 10^16 to avoid integer overflow issues.
- Common mistake: Forgetting to subtract the intersection (multiples of LCM(a, b)) in the inclusion-exclusion principle.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.