algorithmique_bases

Basic algorithm problem and their solutions

1. Two Sum

PROBLEM

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

SOLUTION

One pass

Complexity Analysis

• Time Complexity: O(n). I visit the n elements of the array only once.
• Space Complexity: O(2n). I store at most all the elements of the array and corresponding positions.

SOURCE CODE

g++ source_codes/two_sum.cpp

2. Count Primes

PROBLEM

Count the number of prime numbers less than a non-negative number, n.

SOLUTION

Sieve of Eratosthenes

SCHEMA A FAIRE

Complexity Analysis

• Time Complexity: O(n log n). I visit each odd below n and remove multiples.
• Space Complexity: O(n). I store at most n elements true/false is a prime number condition.

SOURCE CODE

g++ source_codes/count_primes.cpp