Count Primes (Sieve of Eratosthenes)

🎯

Count Primes (Sieve of Eratosthenes)

mediumMATHAmazonGoogleFacebook

Imagine you are a cryptographer who needs to quickly find how many prime numbers exist below a certain threshold to generate secure keys.

💡 This problem is about counting prime numbers up to a limit. Beginners often struggle because checking primality naively for each number is slow, and understanding the sieve method requires grasping how marking multiples eliminates non-primes efficiently.

📋

Problem Statement

Given an integer n, return the number of prime numbers strictly less than n. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

1 ≤ n ≤ 10^5

💡

Example

Input"10"

Output4

The primes less than 10 are 2, 3, 5, and 7.

• n = 0 → 0 (no primes less than 0)
• n = 1 → 0 (no primes less than 1)
• n = 2 → 0 (2 is prime but not less than 2)
• n = 3 → 1 (only prime less than 3 is 2)

⚠️

Common Mistakes

Checking divisibility up to n instead of sqrt(n)

Algorithm runs much slower, possibly timing out.

✅ Only check divisibility up to the square root of the number.

Starting to mark multiples from i instead of i*i in sieve

Redundant marking causes inefficiency and may cause incorrect results.

✅ Start marking multiples from i squared.

Including 0 and 1 as primes

Incorrect prime count and wrong output.

✅ Explicitly mark 0 and 1 as non-prime.

Not handling edge cases like n ≤ 2

Code may crash or return wrong results for small inputs.

✅ Add checks for small inputs and return 0 accordingly.

Marking even numbers in optimized sieve

Wastes time and space, losing optimization benefits.

✅ Skip even numbers after handling 2 separately.

🧠

Brute Force (Check Each Number for Primality)

💡 This approach exists to build foundational understanding of primality testing by checking divisibility for each number, which is intuitive but inefficient for large inputs.

Intuition

For each number less than n, check if it is prime by testing divisibility from 2 up to the square root of that number.

Algorithm

1. Initialize count to 0.
2. For each number i from 2 to n-1:
3. Check if i is prime by testing divisibility from 2 to sqrt(i).
4. If prime, increment count.
5. Return count.

💡 The nested loops make it hard to see efficiency; beginners often miss the sqrt optimization for primality checks.

</>

Code

def countPrimes(n):
    def is_prime(x):
        if x < 2:
            return False
        for i in range(2, int(x**0.5) + 1):
            if x % i == 0:
                return False
        return True

    count = 0
    for num in range(2, n):
        if is_prime(num):
            count += 1
    return count

# Driver code
if __name__ == '__main__':
    print(countPrimes(10))  # Output: 4

Line Notes

def is_prime(x):Defines a helper function to check primality of a single number.

if x < 2:Primes start from 2, so numbers less than 2 are not prime.

for i in range(2, int(x**0.5) + 1):Only check divisors up to sqrt(x) to reduce unnecessary checks.

if x % i == 0:If divisible by any i, x is not prime.

count = 0Initialize counter for prime numbers found.

for num in range(2, n):Check every number from 2 up to n-1 for primality.

if is_prime(num):Increment count if num is prime.

return countReturn total count of primes found.

public class CountPrimesBrute {
    public static boolean isPrime(int x) {
        if (x < 2) return false;
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) return false;
        }
        return true;
    }

    public static int countPrimes(int n) {
        int count = 0;
        for (int num = 2; num < n; num++) {
            if (isPrime(num)) count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countPrimes(10)); // Output: 4
    }
}

Line Notes

public static boolean isPrime(int x) {Helper method to check if x is prime.

if (x < 2) return false;Numbers less than 2 are not prime.

for (int i = 2; i * i <= x; i++) {Check divisors only up to sqrt(x) for efficiency.

if (x % i == 0) return false;If divisible, x is not prime.

int count = 0;Initialize prime count.

for (int num = 2; num < n; num++) {Iterate through numbers less than n.

if (isPrime(num)) count++;Increment count if prime.

return count;Return total prime count.

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) return false;
    }
    return true;
}

int countPrimes(int n) {
    int count = 0;
    for (int num = 2; num < n; num++) {
        if (isPrime(num)) count++;
    }
    return count;
}

int main() {
    cout << countPrimes(10) << endl; // Output: 4
    return 0;
}

Line Notes

bool isPrime(int x) {Function to check primality of x.

if (x < 2) return false;Exclude numbers less than 2.

for (int i = 2; i <= sqrt(x); i++) {Check divisors up to sqrt(x) for efficiency.

if (x % i == 0) return false;If divisible, x is not prime.

int count = 0;Initialize count of primes.

for (int num = 2; num < n; num++) {Check each number less than n.

if (isPrime(num)) count++;Increment count if prime.

return count;Return total prime count.

function isPrime(x) {
    if (x < 2) return false;
    for (let i = 2; i <= Math.sqrt(x); i++) {
        if (x % i === 0) return false;
    }
    return true;
}

function countPrimes(n) {
    let count = 0;
    for (let num = 2; num < n; num++) {
        if (isPrime(num)) count++;
    }
    return count;
}

// Test
console.log(countPrimes(10)); // Output: 4

Line Notes

function isPrime(x) {Defines primality check function.

if (x < 2) return false;Exclude numbers less than 2.

for (let i = 2; i <= Math.sqrt(x); i++) {Check divisors only up to sqrt(x).

if (x % i === 0) return false;If divisible, not prime.

let count = 0;Initialize prime count.

for (let num = 2; num < n; num++) {Iterate through numbers less than n.

if (isPrime(num)) count++;Increment count if prime.

return count;Return total count.

⏱

Complexity

TimeO(n * sqrt(n))

SpaceO(1)

For each number up to n, we check divisibility up to its square root, resulting in roughly n * sqrt(n) operations.

💡 For n=20, this means about 20 * 4.5 = 90 checks, which is manageable but grows quickly for larger n.

Interview Verdict: TLE for large n

This approach is too slow for large inputs, but it helps understand primality checking before moving to efficient methods.

🧠

Sieve of Eratosthenes (Marking Multiples)

💡 This approach introduces the sieve method, which efficiently marks non-prime numbers by iteratively marking multiples, drastically reducing redundant checks.

Intuition

Create a boolean array representing numbers up to n, mark multiples of each prime starting from 2 as non-prime, then count the remaining primes.

Algorithm

1. Initialize a boolean array is_prime of size n with True, except indices 0 and 1 set to False.
2. For each number i from 2 to sqrt(n):
3. If is_prime[i] is True, mark all multiples of i starting from i*i as False.
4. Count the number of True values in is_prime and return it.

💡 The key insight is starting marking from i*i to avoid redundant work, which can be subtle for beginners.

</>

Code

def countPrimes(n):
    if n <= 2:
        return 0
    is_prime = [True] * n
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n, i):
                is_prime[j] = False
    return sum(is_prime)

# Driver code
if __name__ == '__main__':
    print(countPrimes(10))  # Output: 4

Line Notes

if n <= 2:No primes less than 2, handle small input edge case.

is_prime = [True] * nInitialize all as potentially prime.

is_prime[0] = False is_prime[1] = False0 and 1 are not prime by definition.

for i in range(2, int(n**0.5) + 1):Only need to check up to sqrt(n) for marking multiples.

if is_prime[i]:Only mark multiples if i is still considered prime.

for j in range(i*i, n, i):Start marking multiples from i squared to avoid redundant marking.

is_prime[j] = FalseMark multiples as non-prime.

return sum(is_prime)Count how many numbers remain prime.

public class CountPrimesSieve {
    public static int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] isPrime = new boolean[n];
        for (int i = 2; i < n; i++) isPrime[i] = true;
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countPrimes(10)); // Output: 4
    }
}

Line Notes

if (n <= 2) return 0;Handle edge cases where no primes exist.

boolean[] isPrime = new boolean[n];Create array to track primality.

for (int i = 2; i < n; i++) isPrime[i] = true;Initialize all numbers >=2 as prime candidates.

for (int i = 2; i * i < n; i++) {Only iterate up to sqrt(n) for marking.

if (isPrime[i]) {Only mark multiples if i is prime.

for (int j = i * i; j < n; j += i) {Mark multiples starting from i squared.

isPrime[j] = false;Mark multiples as non-prime.

int count = 0;Initialize prime count.

if (isPrime[i]) count++;Count primes remaining.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int countPrimes(int n) {
    if (n <= 2) return 0;
    vector<bool> isPrime(n, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}

int main() {
    cout << countPrimes(10) << endl; // Output: 4
    return 0;
}

Line Notes

if (n <= 2) return 0;Handle small inputs with no primes.

vector<bool> isPrime(n, true);Initialize vector marking all as prime candidates.

isPrime[0] = false; isPrime[1] = false;0 and 1 are not prime.

for (int i = 2; i * i < n; i++) {Only iterate up to sqrt(n) for marking multiples.

if (isPrime[i]) {Only mark multiples if i is prime.

for (int j = i * i; j < n; j += i) {Mark multiples starting from i squared.

isPrime[j] = false;Mark multiples as non-prime.

int count = 0;Initialize prime count.

if (isPrime[i]) count++;Count primes.

function countPrimes(n) {
    if (n <= 2) return 0;
    const isPrime = new Array(n).fill(true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    let count = 0;
    for (let i = 2; i < n; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}

// Test
console.log(countPrimes(10)); // Output: 4

Line Notes

if (n <= 2) return 0;Handle edge cases with no primes.

const isPrime = new Array(n).fill(true);Initialize array marking all as prime candidates.

isPrime[0] = false; isPrime[1] = false;0 and 1 are not prime.

for (let i = 2; i * i < n; i++) {Iterate only up to sqrt(n) for marking multiples.

if (isPrime[i]) {Only mark multiples if i is prime.

for (let j = i * i; j < n; j += i) {Mark multiples starting from i squared.

isPrime[j] = false;Mark multiples as non-prime.

let count = 0;Initialize prime count.

if (isPrime[i]) count++;Count primes.

⏱

Complexity

TimeO(n log log n)

SpaceO(n)

The sieve marks multiples efficiently, resulting in near-linear time complexity with a small logarithmic factor.

💡 For n=10^5, this approach performs roughly 1 million operations, which is efficient for modern computers.

Interview Verdict: Accepted

This is the standard efficient solution for counting primes up to n and is expected in interviews.

🧠

Optimized Sieve (Skip Even Numbers Except 2)

💡 This approach optimizes the sieve by skipping even numbers after handling 2, reducing the number of iterations and memory usage roughly by half.

Intuition

Since all even numbers except 2 are not prime, we can represent only odd numbers in the sieve and mark multiples accordingly.

Algorithm

1. If n ≤ 2, return 0.
2. Initialize a boolean array is_prime for odd numbers only, size roughly n/2, all True.
3. Iterate i from 3 to sqrt(n) stepping by 2:
4. If is_prime[i//2] is True, mark multiples of i starting from i*i, stepping by 2*i, as False.
5. Count primes by adding 1 for prime 2 plus the count of True in is_prime.

💡 Mapping indices to odd numbers and starting marking from i*i with step 2*i can be tricky to visualize.

</>

Code

def countPrimes(n):
    if n <= 2:
        return 0
    is_prime = [True] * (n // 2)
    is_prime[0] = False  # 1 is not prime
    for i in range(3, int(n**0.5) + 1, 2):
        if is_prime[i // 2]:
            for j in range(i * i, n, 2 * i):
                is_prime[j // 2] = False
    return 1 + sum(is_prime)  # add prime 2

# Driver code
if __name__ == '__main__':
    print(countPrimes(10))  # Output: 4

Line Notes

if n <= 2:Handle small inputs with no primes.

is_prime = [True] * (n // 2)Only track odd numbers, halving space.

is_prime[0] = FalseIndex 0 corresponds to number 1, which is not prime.

for i in range(3, int(n**0.5) + 1, 2):Iterate only over odd numbers up to sqrt(n).

if is_prime[i // 2]:Check if current odd number is prime candidate by mapping number i to index i//2.

for j in range(i * i, n, 2 * i):Mark multiples of i starting from i squared, stepping by 2*i to stay odd.

is_prime[j // 2] = FalseMark multiples as non-prime using index mapping j//2.

return 1 + sum(is_prime)Add 1 for prime number 2 plus count of odd primes.

public class CountPrimesOptimizedSieve {
    public static int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] isPrime = new boolean[n / 2];
        for (int i = 0; i < n / 2; i++) isPrime[i] = true;
        isPrime[0] = false; // 1 is not prime
        for (int i = 3; i * i < n; i += 2) {
            if (isPrime[i / 2]) {
                for (int j = i * i; j < n; j += 2 * i) {
                    isPrime[j / 2] = false;
                }
            }
        }
        int count = 1; // count prime 2
        for (int i = 1; i < n / 2; i++) {
            if (isPrime[i]) count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countPrimes(10)); // Output: 4
    }
}

Line Notes

if (n <= 2) return 0;Handle edge cases with no primes less than 2.

boolean[] isPrime = new boolean[n / 2];Track only odd numbers to save space.

for (int i = 0; i < n / 2; i++) isPrime[i] = true;Initialize all odd numbers as prime candidates.

isPrime[0] = false;Index 0 corresponds to number 1, which is not prime.

for (int i = 3; i * i < n; i += 2) {Iterate over odd numbers only up to sqrt(n).

if (isPrime[i / 2]) {Check if current odd number i is prime candidate by mapping to index i/2.

for (int j = i * i; j < n; j += 2 * i) {Mark multiples of i starting from i squared, stepping by 2*i to stay odd.

isPrime[j / 2] = false;Mark multiples as non-prime using index mapping j/2.

int count = 1;Start count with prime 2 included explicitly.

for (int i = 1; i < n / 2; i++) {Iterate over odd number indices to count primes.

if (isPrime[i]) count++;Increment count for each odd prime found.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int countPrimes(int n) {
    if (n <= 2) return 0;
    vector<bool> isPrime(n / 2, true);
    isPrime[0] = false; // 1 is not prime
    for (int i = 3; i * i < n; i += 2) {
        if (isPrime[i / 2]) {
            for (int j = i * i; j < n; j += 2 * i) {
                isPrime[j / 2] = false;
            }
        }
    }
    int count = 1; // count prime 2
    for (int i = 1; i < n / 2; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}

int main() {
    cout << countPrimes(10) << endl; // Output: 4
    return 0;
}

Line Notes

if (n <= 2) return 0;Handle small inputs with no primes less than 2.

vector<bool> isPrime(n / 2, true);Track only odd numbers to save space.

isPrime[0] = false;Index 0 corresponds to number 1, which is not prime.

for (int i = 3; i * i < n; i += 2) {Iterate over odd numbers only up to sqrt(n).

if (isPrime[i / 2]) {Check if current odd number i is prime candidate by mapping to index i/2.

for (int j = i * i; j < n; j += 2 * i) {Mark multiples starting from i squared, stepping by 2*i to stay odd.

isPrime[j / 2] = false;Mark multiples as non-prime using index mapping j/2.

int count = 1;Start count with prime 2 included explicitly.

for (int i = 1; i < n / 2; i++) {Iterate over odd number indices to count primes.

if (isPrime[i]) count++;Increment count for each odd prime found.

function countPrimes(n) {
    if (n <= 2) return 0;
    const isPrime = new Array(Math.floor(n / 2)).fill(true);
    isPrime[0] = false; // 1 is not prime
    for (let i = 3; i * i < n; i += 2) {
        if (isPrime[Math.floor(i / 2)]) {
            for (let j = i * i; j < n; j += 2 * i) {
                isPrime[Math.floor(j / 2)] = false;
            }
        }
    }
    let count = 1; // count prime 2
    for (let i = 1; i < isPrime.length; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}

// Test
console.log(countPrimes(10)); // Output: 4

Line Notes

if (n <= 2) return 0;Handle small inputs with no primes less than 2.

const isPrime = new Array(Math.floor(n / 2)).fill(true);Track only odd numbers to save space.

isPrime[0] = false;Index 0 corresponds to number 1, which is not prime.

for (let i = 3; i * i < n; i += 2) {Iterate over odd numbers only up to sqrt(n).

if (isPrime[Math.floor(i / 2)]) {Check if current odd number i is prime candidate by mapping to index i/2.

for (let j = i * i; j < n; j += 2 * i) {Mark multiples starting from i squared, stepping by 2*i to stay odd.

isPrime[Math.floor(j / 2)] = false;Mark multiples as non-prime using index mapping j/2.

let count = 1;Start count with prime 2 included explicitly.

for (let i = 1; i < isPrime.length; i++) {Iterate over odd number indices to count primes.

if (isPrime[i]) count++;Increment count for each odd prime found.

⏱

Complexity

TimeO(n log log n)

SpaceO(n/2)

By skipping even numbers, we reduce the space and time roughly by half compared to the standard sieve.

💡 For n=10^5, this optimization saves memory and speeds up execution noticeably.

Interview Verdict: Accepted

This is a practical optimization of the sieve that shows deeper mastery and is useful in interviews for demonstrating efficiency improvements.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the standard Sieve of Eratosthenes (Approach 2) is sufficient and optimal. The brute force is useful to explain but not to implement fully. The optimized sieve is a bonus to show deeper understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * sqrt(n))	O(1)	No	N/A	Mention only - never code
2. Sieve of Eratosthenes	O(n log log n)	O(n)	No	N/A	Code this as standard solution
3. Optimized Sieve (Skip Even Numbers)	O(n log log n)	O(n/2)	No	N/A	Mention or code if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding, followed by the sieve method as the optimal solution. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce the Sieve of Eratosthenes and explain how it marks multiples.Step 4: Discuss optimizations like skipping even numbers.Step 5: Code the solution and test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of primality, ability to optimize naive solutions, and knowledge of classic algorithms like the sieve. They also assess your coding accuracy and handling of edge cases.

Common Follow-ups

• How would you count primes in a range [m, n]? → Use a segmented sieve.
• Can you optimize space further? → Use bitsets or only store odd numbers.

💡 These follow-ups test your ability to extend the sieve to ranges and optimize memory, common in advanced interview questions.

🔍

Pattern Recognition

When to Use

1) Need to find/count primes up to n; 2) Problem involves prime checking repeatedly; 3) Constraints too large for naive primality; 4) Efficient marking or elimination of multiples is possible.

Signature Phrases

count primes less than nprime numbers up to nmark multiples

NOT This Pattern When

Naive primality checks without optimization or problems focused on prime factorization without counting primes.

Similar Problems

Find the nth Prime Number - uses sieve to generate primes in orderPrime Factorization - uses primes generated by sieve for factorizationSegmented Sieve - extension to count primes in large ranges

Practice

1. You are given a set of points on a 2D plane and need to find the maximum number of points that lie on the same straight line. Which approach guarantees an optimal solution for this problem?

easy

A. Use a greedy approach by sorting points and connecting consecutive points only.

B. Use a divide-and-conquer approach by splitting points into halves and merging results.

C. Use dynamic programming to build up solutions based on subproblems of smaller point sets.

D. Use a nested loop to consider every pair of points, compute slopes as reduced fractions, and count points sharing the same slope from each base point.

Solution

1. Step 1: Understand problem requirements

   The problem requires finding the maximum number of points on a single line, which depends on slopes between points.

2. Step 2: Identify approach that handles all pairs and slope normalization

   Only the nested loop approach with slope normalization (reduced fractions) correctly groups points on the same line and handles duplicates and vertical lines.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops with slope hashing is the standard optimal approach [OK]

Hint: Check if approach handles all pairs and slope normalization [OK]

Common Mistakes:

• Assuming greedy or DP solves this geometry problem optimally

2. Consider the following code snippet that checks if a number is a palindrome by reversing half of its digits. What is the value of reversed_half after the second iteration of the while loop when input is 12321?

easy

A. 12

B. 1

C. 21

D. 123

Solution

1. Step 1: Trace first iteration

   Initial x=12321, reversed_half=0 reversed_half = 0*10 + 12321%10 = 1 x = 12321 // 10 = 1232

2. Step 2: Trace second iteration

   reversed_half = 1*10 + 1232%10 = 10 + 2 = 12 x = 1232 // 10 = 123

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   After two iterations reversed_half is 12 [OK]

Hint: Track variable updates carefully each loop iteration [OK]

Common Mistakes:

• Off-by-one iteration count
• Mixing x and reversed_half values
• Incorrect modulo or division

3. You are given two rectangles on a 2D plane, each defined by their bottom-left and top-right coordinates. You need to determine if they overlap (i.e., share any area). Which approach guarantees an optimal and correct solution for this problem?

easy

A. Use a greedy algorithm to iteratively check if one rectangle can be shifted to overlap the other.

B. Check if the projections of the rectangles on both the x-axis and y-axis overlap using min and max coordinate comparisons.

C. Apply dynamic programming to store intermediate overlap states between sub-rectangles.

D. Use a brute force grid scan to check every point inside the bounding box of both rectangles.

Solution

1. Step 1: Understand the problem requires checking overlap on both axes

   Rectangles overlap if and only if their projections on the x-axis and y-axis overlap simultaneously.

2. Step 2: Recognize that comparing min and max coordinates on each axis is optimal

   Using min and max to find the intersection length on each axis is a constant-time, direct mathematical check.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Checking intervals on both axes ensures correct overlap detection [OK]

Hint: Check overlap on both x and y axes using min/max [OK]

Common Mistakes:

• Assuming overlap if only one axis overlaps
• Trying to solve with DP or greedy unnecessarily
• Using brute force scanning which is inefficient

4. You need to find the nth number whose prime factors only include 2, 3, and 5. Which approach guarantees an optimal solution that efficiently generates these numbers without checking every integer sequentially?

easy

A. Use a min-heap (priority queue) to always extract the smallest candidate and generate new multiples, avoiding duplicates.

B. Use a greedy algorithm that picks the smallest next multiple of 2, 3, or 5 from previously found numbers.

C. Use dynamic programming with a 2D table to store all factors and their counts for each number up to n.

D. Use brute force by checking each integer sequentially and verifying if its prime factors are only 2, 3, and 5.

Solution

1. Step 1: Understand the problem constraints

   The problem requires generating numbers whose prime factors are only 2, 3, and 5, known as ugly numbers.

2. Step 2: Evaluate approaches for efficiency and correctness

   Brute force is too slow; min-heap approach is efficient but can be optimized further; dynamic programming with a 2D table is overcomplicated. The greedy approach with three pointers picks the smallest next multiple of 2, 3, or 5 from previously found numbers, efficiently generating the sequence without duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three-pointer greedy approach efficiently generates ugly numbers in ascending order without duplicates [OK]

Hint: Three-pointer greedy approach avoids duplicates and generates numbers in order [OK]

Common Mistakes:

• Assuming min-heap is the only efficient approach
• Thinking DP with 2D table is needed for prime factorization
• Believing brute force is efficient enough for large n

5. What is the time complexity of the iterative approach with precomputed powers for converting an Excel column title of length n to its column number?

medium

A. O(n) because powers are computed in a single backward pass and result in a single forward pass

B. O(1) since the alphabet size is fixed at 26

C. O(n^2) due to nested loops for powers and summation

D. O(n log n) due to multiplication of large numbers

Solution

1. Step 1: Identify loops in the code

   There are two loops: one backward to compute powers (runs n-1 times), and one forward to compute the result (runs n times).

2. Step 2: Analyze complexity of each loop

   Both loops run in O(n) time, no nested loops, so total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear passes over input string -> O(n) time [OK]

Hint: Two separate linear passes, no nested loops [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Ignoring fixed alphabet size
• Confusing multiplication cost with complexity