Algorithms in Python

Programming challenges and algorithm implementations in Python 3.

Table of Contents

• Objective
• Programming Challenges
  • Maximum Pairwise Product
  • Fibonacci Number
  • Fibonacci Last Digit
  • Greatest Common Divisor
  • Least Common Multiple
  • Fibonacci Huge Number
  • Fibonacci Sum Last Digit
  • Fibonacci Partial Sum Last Digit
  • Fibonacci Sum Of Squares Last Digit
• Greedy Algorithms
  • Money Change
  • Fractional Knapsack
  • Car Fueling
  • Maximum Dot Product
  • Covering Segments By Points
  • Maximum Number Of Prizes
  • Maximum Salary
• Divide and Conquer
  • Binary Search
  • Majority Element
  • 3 Way Partition Quicksort
  • Number Of Inversions
  • Organizing A Loterry
  • Closest Points
• Technologies
• License

Objective

Practice implementing various algorithms in Python and gain experience designing algorithms.

Programming Challenges

Maximum Pairwise Product

Find the maximum product of two distinct numbers in a sequence of non-negative integers.
Input: A sequence of non-negative integers (2 ≤ n ≤ 2*10E5).
Output: The maximum value that can be obtained by multiplying two different elements from the sequence (0 ≤ a1,...,an ≤ 2*10E5).
Solution

Fibonacci Number

Given an integer n, find the nth Fibonacci number 𝐹𝑛.
Input: Single integer n (0 ≤ n ≤ 45).
Output: nth Fibonacci number.
Solution

Fibonacci Last Digit

Given an integer n, find the last digit of the nth Fibonacci number 𝐹𝑛.
Input: Single integer n (0 ≤ n ≤ 10E7).
Output: Last digit of Fn (where digit is Fn mod 10).
Solution

Greatest Common Divisor

Given two integers a and b, find their greatest common divisor.
Input: Two integers a and b seperated by a space (1 ≤ a, b ≤ 2*10E9).
Output: Greatest common divisor of a and b.
Solution

Least Common Multiple

Given two integers a and b, find their least common multiple.
Input: Two integers a and b seperated by a space (1 ≤ a, b ≤ 2*10E7).
Output: Least common multiple of a and b.
Solution

Fibonacci Huge Number

Given two integers 𝑛 and 𝑚, output 𝐹𝑛 mod m.
Input: Two integers 𝑛 and 𝑚 separated by a space. (1 ≤ 𝑛 ≤ 10E14; 2 ≤ 𝑚 ≤ 10E3).
Output: 𝐹𝑛 mod 𝑚.
Solution

Fibonacci Sum Last Digit

Given an integer 𝑛, find the last digit of the sum 𝐹0 + 𝐹1 +···+ 𝐹𝑛.
Input: Single integer 𝑛 (0 ≤ 𝑛 ≤ 10E14).
Output: The last digit of 𝐹0 + 𝐹1 +···+ 𝐹𝑛.
Solution

Fibonacci Partial Sum Last Digit

Given two non-negative integers 𝑚 and 𝑛, where 𝑚 ≤ 𝑛, find the last digit of the sum 𝐹𝑚 + 𝐹𝑚+1 +···+ 𝐹𝑛.
Input: Two non-negative integers 𝑚 and 𝑛 separated by a space (0 ≤ 𝑚 ≤ 𝑛 ≤ 10E14).
Output: The last digit of 𝐹𝑚 + 𝐹𝑚+1 +···+ 𝐹𝑛.
Solution

Fibonacci Sum Of Squares Last Digit

Compute the last digit of 𝐹0^2 + 𝐹1^2 +···+ 𝐹𝑛^2.
Input: Integer 𝑛 (0 ≤ 𝑛 ≤ 10E14).
Output: The last digit of 𝐹0^2 + 𝐹1^2 +···+ 𝐹𝑛^2.
Solution

Greedy Algorithms

Money Change

Goal is to find the minimum number of coins needed to change the input value into coins with denominations 1, 5, and 10.
Input: Single integer 𝑚 (1 ≤ 𝑚 ≤ 10E3).
Output: The minimum number of coins with denominations 1, 5, 10 that changes 𝑚.
Solution

Fractional Knapsack

Implement an algorithm for the fractional knapsack problem.
Input: First line contains the number 𝑛 of items and the capacity W of a knapsack. Following 𝑛 lines define the values and the weights of the items. The i-th line contains integers 𝑣𝑖 and 𝑤𝑖, the value and weight of the i-th item, respectively (1 ≤ 𝑛 ≤ 10E3, 0 ≤ 𝑊 ≤ 2·10E6; 0 ≤ 𝑣𝑖 ≤ 2·10E6, 0 < 𝑤𝑖 ≤2·10E6 for all 1 ≤ 𝑖 ≤ 𝑛).
Output: The maximal value of fractions of items that fit into the knapsack. The output has to have at least four digits after the decimal point.
Solution

Car Fueling

What is the minimum number of refills needed to travel to another city located 𝑑 miles away. The car starts with a full tank and can travel 𝑚 miles on a full tank. Along the journey there are gas stations at distances stop1, stop2,..., stop𝑛.
Input: Firt line contains an integer 𝑑. Second line contains an integer 𝑚. The third line specifies an integer 𝑛. The last line contains integers stop1, stop2,..., stop𝑛 (1 ≤ 𝑑 ≤ 10E5; 1 ≤ 𝑚 ≤ 400; 1 ≤ 𝑛 ≤ 300; 0 < stop1 < stop2 <···< stop𝑛 < 𝑑).
Output: The minimum number of refills needed, assuming the car starts with a full tank. If it is not possible to reach the destination, output -1.
Solution

Maximum Dot Product

Given two sequences 𝑎1,𝑎2,...,𝑎𝑛 (𝑎𝑖 is the profit per click of the 𝑖-th ad) and 𝑏1,𝑏2,...,𝑏𝑛 (𝑏𝑖 is the average number of clicks per day of the 𝑖-th slot), we need to partition them into 𝑛 pairs (𝑎𝑖,𝑏𝑗) such that the sum of their products is maximized.
Input: The first line contains an integer 𝑛, the second one contains a sequence of integers 𝑎1,𝑎2,...,𝑎𝑛, the third one contains a sequence of integers 𝑏1,𝑏2,...,𝑏𝑛 (1 ≤ 𝑛 ≤ 10E3; −10E5 ≤ 𝑎𝑖,𝑏𝑖 ≤ 10E5 for all 1 ≤ 𝑖 ≤ 𝑛).
Output: The maximum value of ∑︀ 𝑎𝑖𝑐𝑖, where 𝑐1,𝑐2,...,𝑐𝑛 is a permutation of 𝑏1,𝑏2,...,𝑏𝑛.
Solution

Covering Segments By Points

Given a set of 𝑛 segments {(𝑎0,𝑏0),(𝑎1,𝑏1),...,(𝑎𝑛−1,𝑏𝑛−1)} with integer coordinates on a line, find the minimum number 𝑚 of points such that each segment contains at least one point. That is, find a set of integers 𝑋 of the minimum size such that for any segment (𝑎𝑖,𝑏𝑖) there is a point 𝑥 ∈ 𝑋 such that 𝑎𝑖 ≤ 𝑥 ≤ 𝑏𝑖.
Input: The first line of the input contains the number 𝑛 of segments. Each of the following 𝑛 lines contains two integers 𝑎𝑖 and 𝑏𝑖 (separated by a space) defining the coordinates of endpoints of the 𝑖-th segment (1 ≤ 𝑛 ≤ 100; 0 ≤ 𝑎𝑖 ≤ 𝑏𝑖 ≤ 10E9 for all 0 ≤ 𝑖 < 𝑛).
Output: The minimum number 𝑚 of points on the first line and the integer coordinates of 𝑚 points (separated by spaces) on the second line.
Solution

Maximum Number Of Prizes

The goal of this problem is to represent a given positive integer 𝑛 as a sum of as many pairwise distinct positive integers as possible. That is, to find the maximum 𝑘 such that 𝑛 can be written as 𝑎1+𝑎2+···+𝑎𝑘 where 𝑎1,...,𝑎𝑘 are positive integers and 𝑎𝑖 != 𝑎𝑗 for all 1 ≤ 𝑖 < 𝑗 ≤ 𝑘.
Input: A single integer n (1 ≤ 𝑛 ≤ 10E9).
Output: In the first line, output the maximum number 𝑘 such that 𝑛 can be represented as a sum of 𝑘 pairwise distinct positive integers. In the second line, output 𝑘 pairwise distinct positive integers that sum up to 𝑛 (if they exist).
Solution

Maximum Salary

The goal is to composes the largest number out of a set of integers.
Input: First line contains an integer n. Second line contains integers separated by a space (1 ≤ 𝑛 ≤ 100; 1 ≤ 𝑎𝑖 ≤ 10E3 for all 1 ≤ 𝑖 ≤ 𝑛).
Output: The largest number that can be composed out of a1,a2,...,an.
Solution

Divide and Conquer

Binary Search

The goal is to implement the binary search algorithm.
Input: The first line of the input contains an integer 𝑛 and a sequence 𝑎0 < 𝑎1 < . . . < 𝑎𝑛−1 of 𝑛 pairwise distinct positive integers in increasing order. The next line contains an integer 𝑘 and 𝑘 positive integers 𝑏0, 𝑏1, . . . , 𝑏𝑘−1 (1 ≤ 𝑘 ≤ 10E5; 1 ≤ 𝑛 ≤ 3·10E4; 1 ≤ 𝑎𝑖 ≤10E9 for all 0 ≤ 𝑖 < 𝑛; 1 ≤ 𝑏𝑗 ≤ 10E9 for all 0 ≤ 𝑗 < 𝑘).
Output: For all 𝑖 from 0 to 𝑘−1, output an index 0 ≤ 𝑗 ≤ 𝑛−1 such that 𝑎𝑗 = 𝑏𝑖 or −1 if there is no such index.
Solution

Majority Element

Check whether an input sequence contains a majority element.
Input: The first line contains an integer 𝑛, the next one contains a sequence of 𝑛 non-negative integers 𝑎0,𝑎1,...,𝑎𝑛−1 (1 ≤ 𝑛 ≤ 10E5; 0 ≤ 𝑎𝑖 ≤ 10E9 for all 0 ≤ 𝑖 < 𝑛).
Output: 1 if the sequence contains an element that appears strictly more than 𝑛/2 times, and 0 otherwise.
Solution

3 Way Partition Quicksort

Implement the quicksort algorithm to efficiently process a sequences with few unique elements, by implementing a 3-way partition of the array into three parts: < 𝑥 part, = 𝑥 part, and > 𝑥 part.
Input: The first line of the input contains an integer 𝑛. The next line contains a sequence of 𝑛 integers 𝑎0,𝑎1,...,𝑎𝑛−1 (1 ≤ 𝑛 ≤ 10E5; 1 ≤ 𝑎𝑖 ≤ 10E9 for all 0 ≤ 𝑖 < 𝑛).
Output: The sorted sequence in non-decreasing order.
Solution

Number Of Inversions

Count the number of inversions of a given sequence.
Input: The first line contains an integer 𝑛, the next one contains a sequence of integers 𝑎0,𝑎1,...,𝑎𝑛−1 (1 ≤ 𝑛 ≤ 10E5, 1 ≤ 𝑎𝑖 ≤ 10E9 for all 0 ≤ 𝑖 < 𝑛).
Output: Integer of the inversions in the sequence.
Solution

Organizing A Lottery

Given a set of points on a line and a set of segments on a line. The goal is to compute, for each point, the number of segments that contain this point.
Input: The first line contains two non-negative integers 𝑠 and 𝑝 defining the number of segments and the number of points on a line, respectively. The next 𝑠 lines contain two integers 𝑎𝑖,𝑏𝑖 defining the 𝑖-th segment (𝑎𝑖, 𝑏𝑖). The next line contains 𝑝 integers defining points 𝑥1,𝑥2,...,𝑥𝑝 (1 ≤ 𝑠,𝑝 ≤ 50000;−10E8 ≤ 𝑎𝑖 ≤ 𝑏𝑖 ≤ 10E8 for all 0 ≤ 𝑖 < 𝑠; −10E8 ≤ 𝑥𝑗 ≤ 10E8 for all 0 ≤ 𝑗 < 𝑝).
Output: 𝑝 non-negative integers 𝑘0,𝑘1,...,𝑘𝑝−1 where 𝑘𝑖 is the number of segments which contain 𝑥𝑖.
Solution

Closest Points

Given 𝑛 points on a plane, find the smallest distance between a pair of two (different) points.
Input: The first line contains the number 𝑛 of points. Each of the following 𝑛 lines defines a point (𝑥𝑖, 𝑦𝑖) (2 ≤ 𝑛 ≤ 10E5 ; −10E9 ≤ 𝑥𝑖,𝑦𝑖 ≤ 10E9 are integers).
Output: The minimum distance.
Solution

Technologies

Python 3.8

License

This project is licensed under the terms of the MIT license. See the LICENSE file for details.