Codility Lessons

Chapter 1: Iterations

1.1 For Loops

Definition: For loops are used to repeat operations for a specified number of iterations or for each element in a collection.

Syntax: The general syntax is:

for some_variable in range_of_values:
    loop_body

Range Construction: For loops often utilize a range of integers, indicated by range(lowest, highest + 1). For example:
- for i in range(0, 100): print(i) outputs integers from 0 to 99.
- Starting at zero can be simplified: for i in range(100): print(i).

Example: Calculating the factorial of a positive integer n:

factorial = 1
for i in range(1, n + 1):
    factorial *= i

1.2 While Loops

Definition: While loops are employed when the number of iterations is not known beforehand. The loop continues until a specified condition evaluates to false.
Syntax: The syntax is:
```
while some_condition:
    loop_body
```
Example: Counting the number of digits in a positive integer n using arithmetic operations:
```
result = 0
while n > 0:
    n //= 10
    result += 1
```

Another Example: Printing Fibonacci numbers up to n:

a, b = 0, 1
while a <= n:
    print(a)
    a, b = b, a + b

1.3 Looping Over Collections

Definition: Using for loops to iterate over values in various collection types, including lists, sets, and dictionaries.

Example: Looping through a list of days:

days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']
for day in days:
    print(day)

Use of xrange: When dealing with large ranges, consider xrange, which generates values on the fly instead of storing them.
- Basic for loop with a set (order not guaranteed):
```
days_set = set(['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday'])
for day in days_set:
    print(day)
```

Dictionaries: Looping through a dictionary holds keys, producing key-value pair outputs with arbitrary order:

days_dict = {'mon': 'Monday', 'tue': 'Tuesday'}
for key in days_dict:
    print(key, 'stands for', days_dict[key])

Chapter 2: Arrays

2.1 Creating and Accessing Arrays

Definition: Arrays are data structures to store multiple items in a single entity. Example for creating a shopping list:
```
shopping = ['bread', 'butter', 'cheese']
```
Accessing Values: Array elements can be accessed using their index:
```
shopping[0]  # returns 'bread'
```
Arrays also can be empty:
```
shopping = []
```

2.2 Modifying Arrays

Changing Values: Array elements can be modified directly by referencing their index:
```
shopping[1] = 'margarine'
```
Appending Values: Use += to add new items:
```
shopping += ['eggs']
```

2.3 Iterating Over Arrays

Looping through arrays is common for counting or processing all elements. The array's length can be determined via len() function:
```
N = len(shopping)
for i in range(N):
    print(shopping[i])
```
Alternatively, iterating directly through the elements:
```
for item in shopping:
    print(item)
```

Chapter 3: Time Complexity

3.1 Basic Principles

Definition: Time complexity helps estimate the time an algorithm takes to run as the input size grows.
Common Operations: For example, a single addition or assignment doesn’t increase complexity significantly.

3.2 Comparison of Complexities

Constant Time – O(1) remains the same regardless of input size.
Logarithmic Time – O(log n), for example: halving each iteration reduces the number of required operations robustly.
Linear Time – O(n), where the runtime scales directly with output.
Quadratic Time – O(n^2), often seen in algorithms with nested iterations.
Exponential Time – O(2^n) or factorial time O(n!) are impractical for large numbers and require efficient alternatives.

Chapter 10: Prime and Composite Numbers

Prime Numbers: Natural numbers greater than 1 that have exactly two divisors (1 and itself).
Composite Numbers: Numbers with more than two divisors.
Primality Testing: Use methods such as checking divisibility up to √n to efficiently determine if a number is prime.

Examples

Counting Divisors: Iterating through from 1 to n to determine how many number divides n can be improved by checking up to √n.

def divisors(n):
    count = 0
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            count += 1
            if i != n // i:
                count += 1
    return count

Chapter 13: Fibonacci Numbers

Definition: Fibonacci numbers where the first two numbers are 0 and 1 and each subsequent number is the sum of the previous two.
- The recursive Fibonacci method is inefficient due to repeated calculations:
```
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
```

Dynamic Programming Approach: Improves efficiency by storing previously computed values:

def fibonacciDynamic(n):
    fib = [0] * (n + 2)
    fib[1] = 1
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n]

Matrix Multiplication Method: Calculates Fibonacci in O(log n) time utilizing matrix exponentiation for more efficiency:

def fibonacciMatrix(n):
    def multiply(F, M):
        x = F[0]*M[0] + F[1]*M[2]
        y = F[0]*M[1] + F[1]*M[3]
        F[0], F[1] = x, y