Algorithmic Toolbox | Week 2

Last updated: June 19, 2024

Course Name: Algorithmic Toolbox

These are Algorithmic Toolbox Week 2 Programming Assignment Coursera Answers

Programming Assignment: Programming Assignment 2: Algorithmic Warm-up

2-1: Fibonacci Number

def get_nth_fibonacci(n):
    if n <= 1:
        return n

    previous, current = 0, 1

    for _ in range(n - 1):
        previous, current = current, previous + current

    return current

if __name__ == '__main__':
    n = int(input())
    print(get_nth_fibonacci(n))

2-2: Last Digit of a Large Fibonacci Number

def fibonacci_last_digit(n):
    if n <= 1:
        return n

    n = n % 60

    if n <= 1:
        return n

    previous = 0
    current = 1

    for _ in range(n - 1):
        previous, current = current, (previous + current) % 10

    return current

if __name__ == '__main__':
    n = int(input())
    print(fibonacci_last_digit(n))

These are Algorithmic Toolbox Week 2 Programming Assignment Coursera Answers

2-3: Greatest Common Divisor

def gcd(a, b):
    if b == 0:
        return a

    a_prime = a % b
    return gcd(b, a_prime)

if __name__ == '__main__':
    a, b = map(int, input().split())
    print(gcd(a, b))

2-4: Least Common Multiple

from math import gcd

def lcm(a, b):
    """Calculate the lowest common multiple of 2 int's: a, b using `gcd()`."""
    return a * b // gcd(a, b)

if __name__ == '__main__':
    a, b = map(int, input().split())
    print(lcm(a, b))

These are Algorithmic Toolbox Week 2 Programming Assignment Coursera Answers

2-5: Fibonacci Number Again

def get_pisano_period_length(m):
    previous, current = 0, 1
    for i in range(m * m):
        previous, current = current, (previous + current) % m
        # Pisano period always starts with 0, 1
        if previous == 0 and current == 1:
            return i + 1

def fibonacci_huge_optimized(n, m):
    if n <= 1:
        return n

    pisano_period_length = get_pisano_period_length(m)
    n = n % pisano_period_length

    if n <= 1:
        return n

    previous, current = 0, 1
    for _ in range(n - 1):
        previous, current = current, (previous + current) % m

    return current

if __name__ == '__main__':
    n, m = map(int, input().split())
    print(fibonacci_huge_optimized(n, m))

These are Algorithmic Toolbox Week 2 Programming Assignment Coursera Answers

2-6: Last Digit of the Sum of Fibonacci Numbers

def get_pisano_period_length(m):
    previous, current = 0, 1
    for i in range(m * m):
        previous, current = current, (previous + current) % m
        if previous == 0 and current == 1:
            return i + 1

def fibonacci_huge(n, m):
    if n <= 1:
        return n

    pisano_period_length = get_pisano_period_length(m)
    n = n % pisano_period_length

    previous, current = 0, 1
    for _ in range(n - 1):
        previous, current = current, previous + current

    return current % m

def fibonacci_sum(n):
    if n <= 1:
        return n

    # Sum of first n Fibonacci numbers is F(n+2) - 1
    n_plus_2_fib = fibonacci_huge(n + 2, 10)
    sum_fib = n_plus_2_fib - 1

    # Since we are interested in the last digit
    return sum_fib % 10

if __name__ == '__main__':
    n = int(input())
    print(fibonacci_sum(n))

These are Algorithmic Toolbox Week 2 Programming Assignment Coursera Answers

2-7: Last Digit of the Sum of Fibonacci Numbers Again

import sys

def get_pisano_period_length(m):
    previous, current = 0, 1
    for i in range(m * m):
        previous, current = current, (previous + current) % m
        if previous == 0 and current == 1:
            return i + 1

def fibonacci_huge(n, m):
    if n <= 1:
        return n

    pisano_period_length = get_pisano_period_length(m)
    n = n % pisano_period_length

    if n <= 1:
        return n

    previous, current = 0, 1
    for _ in range(n - 1):
        previous, current = current, (previous + current) % m

    return current

def fibonacci_partial_sum(from_, to):
    if to < from_:
        return 0

    sum_to = (fibonacci_huge(to + 2, 10) - 1) % 10
    sum_from = (fibonacci_huge(from_ + 1, 10) - 1) % 10

    result = sum_to - sum_from
    if result < 0:
        result += 10

    return result

if __name__ == '__main__':
    input = sys.stdin.read()
    from_, to = map(int, input.split())
    print(fibonacci_partial_sum(from_, to))

These are Algorithmic Toolbox Week 2 Programming Assignment Coursera Answers

2-8: Last Digit of the Sum of Squares of Fibonacci Numbers

def get_pisano_period_length(m):
    previous, current = 0, 1
    for i in range(m * m):
        previous, current = current, (previous + current) % m
        if previous == 0 and current == 1:
            return i + 1

def fibonacci_huge(n, m):
    if n <= 1:
        return n

    pisano_period_length = get_pisano_period_length(m)
    n = n % pisano_period_length

    if n <= 1:
        return n

    previous, current = 0, 1
    for _ in range(n - 1):
        previous, current = current, (previous + current) % m

    return current

def fibonacci_sum_squares(n):
    if n <= 1:
        return n

    fn = fibonacci_huge(n, 10)
    fn_plus_1 = fibonacci_huge(n + 1, 10)

    return (fn * fn_plus_1) % 10

if __name__ == '__main__':
    n = int(input())
    print(fibonacci_sum_squares(n))

These are Algorithmic Toolbox Week 2 Programming Assignment Coursera Answers

More Weeks of the course: Click Here

More Coursera courses: https://progiez.com/coursera