← IBM Interview Insights

IBM·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

IBM software engineer interview with a single coding problem. Nothing too wild but the overflow gotcha is easy to miss if you're not thinking carefully.

Questions Asked (1)

Q1

Count how many numbers of the form 3^x * 5^y fall within a given range.

Algorithms & Data Structures
Author's notes

Pretty approachable once you realize you just enumerate all valid combinations.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Generate all numbers of the form 3^x * 5^y within the range using nested loops, ensuring no duplicates and stopping when the product exceeds the upper bound. Then count the generated numbers that fall within the range, or use binary search on a precomputed sorted list for efficiency.

Pro tip: Mention that the number of such values is logarithmic in the range, so generation is extremely fast; also discuss handling large ranges by using logarithms to avoid overflow and precomputing for multiple queries.

1. Clarify the problem

Confirm whether the range is inclusive, whether x and y are non-negative integers, and if multiple queries are expected.

2. Choose generation strategy

Decide between generating all numbers up to the upper bound using nested loops, or using binary search on a precomputed list if many queries.

3. Generate numbers efficiently

Use nested loops for x and y, starting from 0, and break when the product exceeds the upper bound. Use multiplication instead of exponentiation for efficiency.

4. Count and handle duplicates

Since 3 and 5 are coprime, all products are unique, so no deduplication is needed. Count those within the range.

5. Analyze complexity and edge cases

Discuss time complexity O(log_3(R) * log_5(R)) and handle edge cases like range boundaries and large numbers.

Key Points to Mention

  • Numbers of the form 3^x * 5^y are 5-smooth numbers with only prime factors 3 and 5.
  • The count is logarithmic in the upper bound, so generation is efficient even for large ranges.
  • Nested loops with early termination avoid unnecessary computations.
  • For multiple queries, precompute a sorted list and use binary search to count in O(log N) per query.
  • Use logarithms to avoid overflow when checking bounds for very large exponents.
  • Since 3 and 5 are coprime, all generated numbers are unique, eliminating duplicate handling.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.