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