Problem Solving Algorithms

1. Algorithm Analysis, Time and Space Complexity

Algorithm analysis involves determining the efficiency of algorithms in terms of time and space
complexity. Here's a breakdown of how to analyze both time and space complexities in Python:

1. Time Complexity

Time complexity is the measure of how the runtime of an algorithm grows with respect to the
input size. It helps to understand the performance of an algorithm as the input grows larger.

Common Time Complexities:

●​ O(1): Constant time – The execution time is constant regardless of input size.
●​ O(log n): Logarithmic time – The execution time grows logarithmically with input size.
●​ O(n): Linear time – The execution time grows linearly with the input size.
●​ O(n log n): Linearithmic time – Common in divide-and-conquer algorithms (e.g.,
merge sort).
●​ O(n²): Quadratic time – Common for algorithms with nested loops (e.g., bubble sort).
●​ O(2^n): Exponential time – The execution time doubles with each additional element
(e.g., recursive Fibonacci).
●​ O(n!): Factorial time – Common in problems like generating all permutations of a set.

Analyzing Time Complexity:

To determine time complexity, consider the following:

●​ Loop Analysis: Count the number of iterations. For example, a loop iterating from 0 to n
contributes O(n).
●​ Nested Loops: Multiply the number of iterations in each nested loop. For example, two
nested loops each iterating from 0 to n contribute O(n²).
●​ Recursion: For recursive algorithms, use recurrence relations to determine time
complexity (e.g., T(n) = 2T(n/2) + O(n) for merge sort).
Example:

# Example of O(n) time complexity

def linear_search(arr, target):
for i in arr:
if i == target:
return True
return False

# Example of O(n^2) time complexity

def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]

2. Space Complexity

Space complexity is the measure of how the memory consumption of an algorithm grows with
the input size.

Common Space Complexities:

●​ O(1): Constant space – The algorithm uses a fixed amount of memory regardless of the
input size.
●​ O(n): Linear space – The algorithm uses space proportional to the input size.
●​ O(n²): Quadratic space – The algorithm uses space proportional to the square of the input
size.
Analyzing Space Complexity:

●​ Variables: Consider the space used by variables and data structures (lists, dictionaries,
etc.).
●​ Recursive Algorithms: Recursion adds space complexity due to the call stack, so
recursive algorithms might use additional space.

Example:

# Example of O(1) space complexity

def print_first_element(arr):
print(arr[0]) # Constant space used regardless of array
size

# Example of O(n) space complexity

def create_new_list(arr):
new_list = []
for i in arr:
new_list.append(i * 2) # The new list has space
proportional to input size
return new_list

3. Big-O Notation

Big-O notation is used to express both time and space complexities. It provides an upper bound
on the growth rate of an algorithm, ensuring that the algorithm will not exceed the given time or
space.

●​ Best Case: The best possible time complexity of the algorithm.

●​ Worst Case: The worst possible time complexity.
●​ Average Case: The expected time complexity on average.
Example of analyzing a recursive algorithm:

# Example of O(2^n) time complexity (recursive Fibonacci)

def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

Conclusion:

By analyzing loops, recursive calls, and space used by data structures, you can determine the
time and space complexity of an algorithm in Python. Remember that Big-O notation helps to
express the worst-case scenario for both time and space complexities.

2. How to solve a problem

To solve a problem effectively, you can follow a structured approach. Here’s a step-by-step guide
that can help you tackle problems systematically:

1. Understand the Problem

●​ Read the Problem Statement Carefully: Make sure you fully understand the problem,
including the input and expected output.
●​ Identify the Goal: What exactly do you need to find or solve?
●​ Clarify Assumptions: Are there any assumptions you need to make (e.g., input range,
constraints, or edge cases)?

2. Break the Problem Down

●​ Divide the Problem into Sub-Problems: If the problem is complex, break it into
smaller, more manageable parts.
●​ Identify Input and Output: List the inputs and expected outputs for each part.
 ●​ Plan for Edge Cases: Consider edge cases, such as empty inputs or extreme values.

3. Devise a Plan

●​ Choose an Approach or Algorithm:

○​ Will you use brute force, a greedy approach, dynamic programming, or another
method?
○​ Choose an algorithm that fits the problem based on time and space constraints.
●​ Consider Data Structures: Decide which data structures would help solve the problem
(arrays, linked lists, trees, stacks, etc.).
●​ Outline the Steps: Write out the steps or algorithm you plan to implement.

4. Implement the Solution

●​ Write Code: Implement the solution based on your plan.

●​ Use Clear and Efficient Code: Aim for clarity and efficiency. Choose concise and
readable code structures.
●​ Test as You Go: Test intermediate steps to ensure the algorithm works as expected.

5. Test the Solution

●​ Test with Sample Inputs: Run your code with sample inputs to verify that it works.
●​ Handle Edge Cases: Test edge cases to ensure robustness (e.g., empty arrays, negative
numbers).
●​ Check Time and Space Complexity: Make sure your solution is efficient enough for the
input size.

6. Optimize the Solution

●​ Analyze Time and Space Complexity: Check whether the solution can be optimized for
better performance.
●​ Refactor for Clarity and Efficiency: If the solution works but could be more efficient or
readable, refactor it.
7. Review and Finalize

●​ Check for Bugs: Review your code and solution to ensure there are no bugs.
●​ Refactor for Better Performance: If necessary, optimize for both time and space.
●​ Document Your Solution: Write comments in your code explaining your thought
process, especially if the solution is complex.

Example: Solving a Simple Problem

Problem: Find the Maximum Element in an Array

●​ Input: An array of integers, e.g., [1, 3, 5, 2, 4].

●​ Output: The maximum element in the array, e.g., 5.

Step-by-Step Solution:

1.​ Understand the Problem:

○​ We need to find the maximum element in the array.
○​ The array can contain positive, negative, and zero values.
2.​ Break the Problem Down:
○​ You can iterate through the array and track the largest value encountered.
3.​ Devise a Plan:
○​ Use a variable to store the maximum value.
○​ Loop through the array, updating the maximum value as you encounter larger
numbers.
4.​ Write the Code:

def find_maximum(arr):
# Initialize the first element as the maximum
max_value = arr[0]

# Iterate through the array to find the maximum value

for num in arr[1:]:
 if num > max_value:
max_value = num

return max_value

5.​ Test the Solution:

arr = [1, 3, 5, 2, 4]
print(find_maximum(arr)) # Output: 5

6.​ Optimize (if necessary):

○​ This solution already has a time complexity of O(n) and space complexity of
O(1), which is optimal for this problem.
7.​ Review:
○​ The solution is simple, efficient, and works for edge cases (e.g., arrays with only
one element, negative numbers).

By following these steps, you can systematically break down and solve a problem. As you gain
experience, you’ll develop your own approach for solving different types of problems.

3. Thinking and Describing a Problem and its Solution

When solving a problem, thinking and describing it clearly is an important part of the process.
Breaking down the problem in a structured way helps you identify key elements and come up
with an effective solution. Here's how to approach both thinking and describing a problem and its
solution:

1. Thinking About the Problem

a. Understand the Problem Statement

●​ What is the goal?

○​ Clarify exactly what the problem is asking for. What is the expected result?
 ●​ What are the inputs and outputs?
○​ Identify the type of inputs (e.g., integers, strings, lists, etc.).
○​ Understand the format of the output (e.g., a single value, a collection of values,
etc.).
●​ What are the constraints?
○​ What is the size of the input?
○​ Are there any limits on values, time, or memory (e.g., the input must be sorted, or
the time limit for running the solution)?

b. Identify the Core Problem

●​ Break down the problem into smaller parts. If it involves multiple steps, consider each
step.
●​ Ask questions: What challenges does the problem present? Is it straightforward, or does
it require deeper insights (like optimization)?
●​ Look for patterns: Can the problem be reduced to a known algorithm or pattern (sorting,
searching, recursion)?

c. Consider Edge Cases

●​ Think about extreme cases such as empty inputs, the smallest or largest values, and the
boundaries of the problem constraints.
●​ How does the problem behave in these edge cases?

d. Formulate a Plan for the Solution

●​ How will you approach solving it? What algorithms, data structures, or techniques will be
necessary to solve the problem efficiently?
●​ Consider the time complexity and space complexity of your potential solution. Are there
optimizations that can be made to improve performance?

2. Describing the Problem and Solution

a. Problem Description
 ●​ State the problem clearly: Explain the problem, inputs, outputs, and constraints in a
simple and concise way. Make sure anyone reading the description can understand the
requirements.
●​ Example Problem Description: "Given an array of integers, return the largest number in
the array. The array may contain both positive and negative integers, and the size of the
array is at most 1000 elements."

b. Approach and Plan

●​ Explain the thought process: Describe how you plan to solve the problem. This could
involve outlining the steps you'll take to implement the solution, including the algorithm
and logic you will use.
●​ Example Plan: "We will iterate over the entire array once, keeping track of the largest
value we encounter. At the end of the loop, we will have the largest number in the array.
This approach ensures we only need one pass over the array, resulting in O(n) time
complexity."

c. Algorithm/Method

●​ Describe the algorithm: If you're using a specific algorithm, explain it in detail. What is
the core idea behind the algorithm? Why does it solve the problem?
●​ Example Algorithm:
○​ Initialize max_value as the first element of the array.
○​ Loop through the array from the second element onward.
○​ If the current element is greater than max_value, update max_value.
○​ Return the max_value after the loop completes.

d. Code Implementation

●​ Provide a clear, concise implementation of the algorithm.

●​ Example Code:

def find_maximum(arr):
# Check if the array is empty
 if not arr:
return None # Edge case: Return None for empty array

max_value = arr[0] # Initialize the first element as the

max value

# Loop through the rest of the array

for num in arr[1:]:
if num > max_value:
max_value = num # Update max_value if a larger
number is found

return max_value # Return the maximum value

e. Time and Space Complexity

●​ Time Complexity: What is the time complexity of the solution, and why? In this case, it is
O(n) because we loop through the entire array once.
●​ Space Complexity: What is the space complexity, and why? In this case, it is O(1)
because we use a fixed amount of extra space (for the max_value variable) regardless
of the size of the input.

f. Testing the Solution

●​ Describe how you will test the solution. What types of test cases will you use? Include
normal cases, edge cases, and possible failure scenarios.
●​ Example Test Cases:
○​ find_maximum([1, 2, 3, 4, 5]) → Expected output: 5
○​ find_maximum([-10, -5, -20]) → Expected output: -5
○​ find_maximum([1]) → Expected output: 1 (Edge case: single element)
 ○​ find_maximum([]) → Expected output: None (Edge case: empty array)

3. Example of Thinking and Describing a Problem

Problem: Reverse a String

●​ Problem Statement: Given a string, return a new string that is the reverse of the original
string.

Thinking about the problem:

●​ The goal is to reverse a string. Since strings are immutable in Python, we'll need to build
a new string.
●​ The input is a string, and the output should also be a string.
●​ We can solve this by iterating through the string backward or using Python's built-in
slicing feature.

Solution Plan:

●​ Approach 1: Use Python's slicing feature to reverse the string.

●​ Approach 2: Use a loop to iterate over the string from the end to the beginning and build
the reversed string.
●​ Both approaches have a time complexity of O(n) and space complexity of O(n), where n
is the length of the string.

Algorithm:

●​ Using slicing: We can reverse the string by using the slicing feature [::-1] in Python.
●​ Using a loop: We can iterate over the string from the end to the beginning, adding
characters to a new string.

Code Implementation:

def reverse_string(s):
return s[::-1] # Using Python slicing to reverse the string
# Alternatively, using a loop
def reverse_string_loop(s):
reversed_str = ''
for char in s[::-1]:
reversed_str += char
return reversed_str

Testing:

print(reverse_string("hello")) # Output: "olleh"

print(reverse_string("Python")) # Output: "nohtyP"
print(reverse_string("")) # Edge case: Empty string, Output: ""

Summary

When solving a problem, it’s important to:

1.​ Think: Understand the problem, break it into sub-problems, identify the approach, and
consider edge cases.
2.​ Describe: Write a clear problem statement, explain the approach, and describe the
algorithm.
3.​ Code: Implement the solution and test it with edge cases.
4.​ Analyze: Understand the time and space complexity of the solution.

By following this structure, you can approach any problem logically and ensure your solution is
both effective and well-documented.
4. Basic mathematical aptitude :
○ prime numbers

Here are several ways to find prime numbers in Python using a function, lambda, and list
comprehension:

1. Using a Function

A standard approach is to create a function that checks if a number is prime.

def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True

# Testing the function

print(is_prime(5)) # True
print(is_prime(10)) # False

Time Complexity:

●​ The loop runs from 2 to n\sqrt{n}n​, so the time complexity is O(√n).

●​ In the worst case (when n is a prime number), the function checks up to the square root
of n.

Space Complexity:

●​ The space complexity is O(1) because we are only using a constant amount of extra space
(no additional data structures are used).
2. Using Lambda Expression

Lambda functions provide a more compact way to express functionality. While it’s generally
used for short, simple functions, it can also be used to check prime numbers.

is_prime_lambda = lambda n: n > 1 and all(n % i != 0 for i in

range(2, int(n**0.5) + 1))

# Testing the lambda function

print(is_prime_lambda(5)) # True
print(is_prime_lambda(10)) # False

Time Complexity:

●​ The all() function iterates over the range from 2 to n\sqrt{n}n​, so the time complexity
is O(√n).

Space Complexity:

●​ The space complexity is O(1), as no extra space is used apart from the input variable.

3. Using List Comprehension

List comprehension is a concise way to generate lists. You can use it to generate a list of prime
numbers up to a certain limit.

def primes_up_to(limit):
return [n for n in range(2, limit + 1) if all(n % i != 0 for
i in range(2, int(n**0.5) + 1))]

# Testing list comprehension

print(primes_up_to(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Time Complexity:

●​ For each number from 2 to limit, we check divisibility up to n\sqrt{n}n​, resulting in a

time complexity of O(limit × √limit).
●​ The outer loop runs limit - 1 times, and for each number, we perform a check with a
complexity of n\sqrt{n}n​.

Space Complexity:

●​ The space complexity is O(limit) because the list comprehension generates a list of
primes, and the space grows linearly with the size of the input.

4. Using Filter and Lambda

You can use the filter() function in combination with a lambda expression to filter out prime
numbers from a list.

def primes_up_to_filter(limit):
return list(filter(lambda n: n > 1 and all(n % i != 0 for i
in range(2, int(n**0.5) + 1)), range(2, limit + 1)))

# Testing filter and lambda

print(primes_up_to_filter(30)) # [2, 3, 5, 7, 11, 13, 17, 19,
23, 29]

Time Complexity:

●​ Similar to list comprehension, this method checks each number in the range up to
limit, resulting in a time complexity of O(limit × √limit).
●​ The filter applies the primality check for each number in the range.

Space Complexity:
 ●​ The space complexity is O(limit) because the output is stored as a list of primes, which
can grow up to limit in size.

5. Using Sieve of Eratosthenes (Efficient Method)

A more efficient algorithm to find all prime numbers up to a given number is the Sieve of
Eratosthenes. It works by marking multiples of each prime starting from 2.

def sieve_of_eratosthenes(limit):
sieve = [True] * (limit + 1)
sieve[0], sieve[1] = False, False
for i in range(2, int(limit**0.5) + 1):
if sieve[i]:
for j in range(i * i, limit + 1, i):
sieve[j] = False
return [i for i in range(2, limit + 1) if sieve[i]]

# Testing the sieve method

print(sieve_of_eratosthenes(30)) # [2, 3, 5, 7, 11, 13, 17, 19,
23, 29]

Time Complexity:

●​ The outer loop runs up to n\sqrt{n}n​, and for each prime number, we mark its multiples
as non-prime. The time complexity is O(n log log n), which is much faster than checking
each number individually.

Space Complexity:

●​ The space complexity is O(n) because we need an array (sieve) of size n to store
boolean values indicating whether each number is prime or not.
Summary of Methods:

1.​ Function: The traditional approach with an explicit function.

2.​ Lambda: A compact inline function for checking primes.
3.​ List Comprehension: A concise way to generate prime numbers in a list.
4.​ Filter + Lambda: Filters prime numbers from a range using filter and lambda.
5.​ Sieve of Eratosthenes: A highly efficient way to find all primes up to a certain limit.

Each method has its use case depending on the problem's requirements for efficiency and
readability.

Summary of Complexities:

Method Time Complexity Space Complexity

Using a Function O(√n) O(1)

Using Lambda O(√n) O(1)

Using List Comprehension O(limit × √limit) O(limit)

Using Filter and Lambda O(limit × √limit) O(limit)

Sieve of Eratosthenes O(n log log n) O(n)

Conclusion:

●​ Simple functions (O(√n)): These methods are good for checking the primality of
individual numbers.
●​ List Comprehension / Filter: Suitable for generating a list of primes but less efficient
for large ranges compared to the sieve method.
●​ Sieve of Eratosthenes (O(n log log n)): The most efficient method for generating all
prime numbers up to a large limit. It should be used when you need all primes in a given
range.
○ prime factors
def prime_factors(n):
factors = []
# Check for number of 2s that divide n
while n % 2 == 0:
[Link](2)
n //= 2
# Check for odd factors from 3 to sqrt(n)
for i in range(3, int(n**0.5) + 1, 2):
while n % i == 0:
[Link](i)
n //= i
# If n is a prime number greater than 2
if n > 2:
[Link](n)
return factors

# Example usage
number = 56
print(f"Prime factors of {number} are: {prime_factors(number)}")

This function first divides the number by 2 as many times as possible, then checks for all odd
numbers up to the square root of the number. If a factor divides the number evenly, it's added to
the list of factors. Finally, if the remaining number is greater than 2, it's a prime factor and is
added to the list.

○ twin primes

Twin primes are pairs of prime numbers that differ by exactly 2. For example, (3, 5) and (11, 13)
are twin primes.
To find twin primes in Python, you can write a function to check for prime numbers and then
look for pairs of primes that differ by 2. Here's an example implementation:

def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True

def twin_primes(limit):
primes = []
for num in range(2, limit):
if is_prime(num) and is_prime(num + 2):
[Link]((num, num + 2))
return primes

# Example usage
limit = 100
print(f"Twin primes up to {limit}: {twin_primes(limit)}")

Explanation:

1.​ The is_prime function checks if a number is prime.

2.​ The twin_primes function iterates through numbers and finds pairs of primes that
differ by exactly 2.
3.​ The result is a list of twin prime pairs up to the specified limit.

In the example usage, the function will print the twin primes up to 100.
○ improving prime number efficiency - sieve of Eratosthenes

To improve the efficiency of finding prime numbers in Python, you can use the Sieve of
Eratosthenes, which is a more efficient algorithm for finding all primes up to a given limit. This
method works by iteratively marking the multiples of each prime number, starting from 2, and
leaves only primes in the list.

Here's an optimized version using the Sieve of Eratosthenes:

def sieve_of_eratosthenes(limit):
# Initialize a list of boolean values to represent primality
primes = [True] * (limit + 1)
primes[0] = primes[1] = False # 0 and 1 are not prime numbers

for i in range(2, int(limit**0.5) + 1):

if primes[i]:
for j in range(i * i, limit + 1, i):
primes[j] = False

return [x for x in range(2, limit + 1) if primes[x]]

# Example usage
limit = 100
prime_numbers = sieve_of_eratosthenes(limit)
print(f"Prime numbers up to {limit}: {prime_numbers}")

Explanation:

1.​ Initialization: The primes list is initialized with True, indicating that all numbers are
initially assumed to be prime.
 2.​ Marking non-primes: Starting from the first prime (2), the algorithm marks all multiples
of each prime as False (not prime). This process continues until the square root of the
limit.
3.​ Return Primes: The final list of primes is extracted from the primes array.

Advantages:

●​ Efficiency: This algorithm runs in O(nlog⁡log⁡n)O(n \log \log n)O(nloglogn), which is

much more efficient than checking primality individually for each number.
●​ Memory Usage: It uses a boolean list to mark primes, which is memory efficient for
large values of n.

For very large numbers, you can use optimizations like segmenting the sieve or implementing
more advanced prime generation techniques, but this is a great starting point for most use cases.

○ perfect numbers

A perfect number is a positive integer that is equal to the sum of its proper divisors (excluding
itself). For example, 6 is a perfect number because its divisors are 1, 2, and 3, and 1+2+3=61 + 2
+ 3 = 61+2+3=6.

To find perfect numbers in Python, you can write a function that checks for each number if it
satisfies this condition. Here's an implementation:

def get_divisors(n):
divisors = []
for i in range(1, n // 2 + 1): # Check divisors up to n//2
if n % i == 0:
[Link](i)
return divisors
def is_perfect_number(n):
return sum(get_divisors(n)) == n

def perfect_numbers(limit):
perfects = []
for num in range(2, limit):
if is_perfect_number(num):
[Link](num)
return perfects

# Example usage
limit = 10000
print(f"Perfect numbers up to {limit}: {perfect_numbers(limit)}")

Explanation:

1.​ get_divisors function: Finds all divisors of a given number nnn by checking all
numbers from 1 to n//2n//2n//2.
2.​ is_perfect_number function: Checks if the sum of the divisors of nnn equals nnn,
confirming it's a perfect number.
3.​ perfect_numbers function: Finds all perfect numbers up to a specified limit.

Example Output:

For a limit of 10000, this will output the perfect numbers up to 10000, such as:

Perfect numbers up to 10000: [6, 28, 496, 8128]

Optimization Considerations:
 ●​ Divisors Calculation: We check up to n//2n//2n//2 for divisors, but a better approach
would be to check only up to n\sqrt{n}n​, and add both divisors iii and n/in/in/i when
n%i==0n \% i == 0n%i==0. This can speed up the divisor summation process.

Here's a more efficient version:

Optimized Perfect Numbers

def get_divisors_optimized(n):
divisors = [1]
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
[Link](i)
if i != n // i:
[Link](n // i)
return divisors

def is_perfect_number_optimized(n):
return sum(get_divisors_optimized(n)) == n

def perfect_numbers_optimized(limit):
perfects = []
for num in range(2, limit):
if is_perfect_number_optimized(num):
[Link](num)
return perfects

# Example usage
limit = 10000
print(f"Perfect numbers up to {limit}:
{perfect_numbers_optimized(limit)}")

This approach is much faster because it reduces the number of divisor checks significantly by
only iterating up to n\sqrt{n}n​.

○ collatz conjecture

The Collatz conjecture is a sequence defined as follows:

1.​ Start with any positive integer nnn.

2.​ If nnn is even, divide it by 2.
3.​ If nnn is odd, multiply it by 3 and add 1.
4.​ Repeat the process with the new value of nnn until nnn becomes 1.

The conjecture states that no matter what value of nnn you start with, you will always eventually
reach 1.

Here’s an implementation of the Collatz conjecture in Python:

Collatz Conjecture Implementation

def collatz_sequence(n):
sequence = [n]
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
[Link](n)
 return sequence

# Example usage
number = 7
print(f"Collatz sequence starting with {number}:
{collatz_sequence(number)}")

Explanation:

1.​ collatz_sequence function: This function generates the Collatz sequence for a
given number nnn. It continues modifying nnn according to the rules of the conjecture
until nnn reaches 1.
2.​ Return Value: The function returns the entire sequence as a list of numbers.

Example Output:

For an input of 7, the output will be:

Collatz sequence starting with 7: [7, 22, 11, 34, 17, 52, 26,
13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

You can modify the input value (number) to experiment with different starting points.

○ Goldbach conjecture

The Goldbach conjecture states that every even integer greater than 2 can be expressed as the
sum of two prime numbers. For example:
 ●​ 4 = 2 + 2
●​ 6 = 3 + 3
●​ 8 = 3 + 5
●​ 10 = 3 + 7

To verify this conjecture in Python, we can write a function that:

1.​ Checks if a number is prime.

2.​ Iterates through all even numbers greater than 2.
3.​ For each even number, checks if it can be written as the sum of two prime numbers.

Goldbach Conjecture Implementation

def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True

def goldbach_conjecture(n):
if n <= 2 or n % 2 != 0:
raise ValueError("Input must be an even integer greater
than 2")

for i in range(2, n // 2 + 1):

if is_prime(i) and is_prime(n - i):
return (i, n - i)
return None
# Example usage
even_number = 28
result = goldbach_conjecture(even_number)
if result:
print(f"Goldbach conjecture for {even_number}: {result[0]} +
{result[1]}")
else:
print(f"No Goldbach pair found for {even_number}")

Explanation:

1.​ is_prime function: This function checks if a number is prime by dividing it from 2 up
to the square root of the number.
2.​ goldbach_conjecture function: This function takes an even integer nnn greater
than 2 and checks if it can be written as the sum of two primes. It iterates through
numbers from 2 to n/2n/2n/2 and checks if both the current number and n−current
numbern - \text{current number}n−current number are prime. If so, it returns the pair of
primes.

Example Output:

For an input of 28, the output will be:

Goldbach conjecture for 28: 5 + 23

This means that 28=5+2328 = 5 + 2328=5+23, which satisfies the Goldbach conjecture. You can
experiment with different even numbers by changing the value of even_number.
○ mean, median, mode, quartiles, std variance, correlation, regression
○ probability and conditional probability basic geometry ideas

1. Mean, Median, Mode, Quartiles, Standard Deviation (Std), Variance

You can use numpy for these calculations:

import numpy as np
from scipy import stats

# Sample data
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# Mean
mean = [Link](data)

# Median
median = [Link](data)

# Mode
mode = [Link](data)[0][0]

# Quartiles
q1, q3 = [Link](data, [25, 75])

# Standard Deviation
std_dev = [Link](data)

# Variance
variance = [Link](data)

print(f"Mean: {mean}")
print(f"Median: {median}")
print(f"Mode: {mode}")
print(f"Quartiles: Q1={q1}, Q3={q3}")
print(f"Standard Deviation: {std_dev}")
print(f"Variance: {variance}")

2. Correlation and Regression

You can calculate correlation and perform simple linear regression using numpy and scipy:

# Sample data for correlation and regression

x = [Link]([1, 2, 3, 4, 5])
y = [Link]([5, 4, 6, 7, 8])

# Correlation
correlation = [Link](x, y)[0, 1]

# Simple Linear Regression

slope, intercept = [Link](x, y, 1)

print(f"Correlation: {correlation}")
print(f"Linear Regression: y = {slope}x + {intercept}")

3. Probability and Conditional Probability

For probability calculations, you can simulate events or calculate basic probabilities using
[Link]:

from [Link] import binom

# Probability of 3 successes in 10 trials, p=0.5

probability = [Link](3, 10, 0.5)

# Conditional Probability: P(A|B) = P(A and B) / P(B)

P_A_and_B = 0.2 # Probability of both A and B occurring
P_B = 0.4 # Probability of B occurring
P_A_given_B = P_A_and_B / P_B

print(f"Probability: {probability}")
print(f"Conditional Probability P(A|B): {P_A_given_B}")

4. Basic Geometry Ideas

For basic geometry, we can use Python to calculate areas and perimeters for common shapes:

import math

# Circle: Area and Circumference

radius = 5
circle_area = [Link] * radius ** 2
circle_circumference = 2 * [Link] * radius

# Triangle: Area (given base and height)

base = 6
height = 8
triangle_area = 0.5 * base * height

# Rectangle: Area and Perimeter

length = 10
width = 4
rectangle_area = length * width
rectangle_perimeter = 2 * (length + width)

print(f"Circle Area: {circle_area}")

print(f"Circle Circumference: {circle_circumference}")
print(f"Triangle Area: {triangle_area}")
print(f"Rectangle Area: {rectangle_area}")
print(f"Rectangle Perimeter: {rectangle_perimeter}")

5. Set representation - DONE

6. Simple data structures – Array, Linked List, stack, queue, vector, map,
hashtable
ARRAY
# Array Implementation
array = [1, 2, 3, 4, 5]
print(array)

LINKED LIST
class Node:
def __init__(self, data):
 [Link] = data
[Link] = None

class LinkedList:
def __init__(self):
[Link] = None

def append(self, data):

new_node = Node(data)
if not [Link]:
[Link] = new_node
else:
current = [Link]
while [Link]:
current = [Link]
[Link] = new_node

def display(self):
current = [Link]
while current:
print([Link], end=" -> ")
current = [Link]
print("None")

# Example
ll = LinkedList()
[Link](1)
[Link](2)
[Link](3)
[Link]()
STACK
class Stack:
def __init__(self):
[Link] = []

def push(self, data):

[Link](data)

def pop(self):
if not self.is_empty():
return [Link]()
else:
return "Stack is empty"

def peek(self):
if not self.is_empty():
return [Link][-1]
else:
return "Stack is empty"

def is_empty(self):
return len([Link]) == 0

# Example
stack = Stack()
[Link](1)
[Link](2)
[Link](3)
print([Link]()) # 3
print([Link]()) # 2
QUEUE
class Queue:
def __init__(self):
[Link] = []

def enqueue(self, data):

[Link](data)

def dequeue(self):
if not self.is_empty():
return [Link](0)
else:
return "Queue is empty"

def front(self):
if not self.is_empty():
return [Link][0]
else:
return "Queue is empty"

def is_empty(self):
return len([Link]) == 0

# Example
queue = Queue()
[Link](1)
[Link](2)
[Link](3)
print([Link]()) # 1
print([Link]()) #2
VECTOR
# Vector Implementation (Same as Array in Python)
vector = [1, 2, 3]
[Link](4) # Adds 4 to the end
print(vector)

MAP
# Map Implementation (Dictionary in Python)
map_example = {'name': 'Alice', 'age': 30}
print(map_example['name']) # Alice
map_example['city'] = 'New York'
print(map_example)

HASHTABLE
# Hashtable Implementation (Dictionary in Python)
hashtable = {'apple': 10, 'banana': 20}
print(hashtable['apple']) # 10
hashtable['orange'] = 30
print(hashtable)

7. simple operations – add, delete, insert and show - DONE

8. Simple problem using these data structures

○ Sorting method

Sorting with [Link] (Frequency Sorting)

If you need to sort based on the frequency of elements, you can use [Link]
to count the elements and then sort by frequency.
sorted(): Returns a sorted list without modifying the original.

[Link](): Sorts the list in place.

Custom sorting: Use key to sort based on custom logic.

heapq: A module for heap-based sorting.

Counter: Can be used for sorting based on frequency.

from collections import Counter

my_list = [3, 1, 4, 1, 5, 9, 2, 6, 1]
count = Counter(my_list)
sorted_by_frequency = sorted([Link](), key=lambda x: x[1],
reverse=True)
print("Sorted by frequency:", sorted_by_frequency)

Sorting 1
def bubble_sort(arr):
n = len(arr)
# Traverse through all elements in the list
for i in range(n):
# Last i elements are already sorted
swapped = False
for j in range(0, n-i-1):
# Swap if the element found is greater than the next
element
 if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
# If no two elements were swapped by the inner loop,
then the list is sorted
if not swapped:
break

# Example
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)

Merge Sort
def merge_sort(arr):
if len(arr) > 1:
# Find the middle of the list
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]

# Recursively split the halves

merge_sort(left_half)
merge_sort(right_half)

# Merge the sorted halves

i = j = k = 0
 # Copy data to temporary arrays L[] and R[]
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1

# Check if any element was left in the left_half

while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1

# Check if any element was left in the right_half

while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1

# Example
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print("Sorted array:", arr)
○ searching – linear search, binary search and hash search
def hash_search(hash_table, target):
return hash_table.get(target, -1) # Return value if found, else return -1

# Example
hash_table = {3: 'a', 5: 'b', 7: 'c', 9: 'd', 11: 'e', 13: 'f'}
target = 9
result = hash_search(hash_table, target)
if result != -1:
print(f"Element found: {result}")
else:
print("Element not found")

○ search and sort functions

Search Functions:

●​ in: Check if an element exists in a collection.

●​ index(): Find the index of an element.
●​ count(): Count occurrences of an element.

Sort Functions:

●​ sorted(): Returns a sorted copy of the list.

●​ sort(): Sorts the list in place.
●​ heapq: For heap-based sorting.

9. Problems based on above topics like finding the minimum and maximum,
def find_min_max(nums):
return min(nums), max(nums)
# Example usage:
nums = [12, 3, 5, 7, 19, 1]
min_val, max_val = find_min_max(nums)
print(f"Minimum value is {min_val}")
print(f"Maximum value is {max_val}")

def find_min_max(nums):
min_val = max_val = nums[0] # Assume first element is both min and max

for num in nums:

if num < min_val:
min_val = num
elif num > max_val:
max_val = num

return min_val, max_val

# Example usage:
nums = [12, 3, 5, 7, 19, 1]
min_val, max_val = find_min_max(nums)
print(f"Minimum value is {min_val}")
print(f"Maximum value is {max_val}")

○ finding the Kth largest element and Kth smallest element,

def find_kth_largest(nums, k):
[Link]()
return nums[-k] # Kth largest

def find_kth_smallest(nums, k):

[Link]()
 return nums[k-1] # Kth smallest

# Example usage:
nums = [12, 3, 5, 7, 19, 1]
k=2
print(f"{k}th largest element is {find_kth_largest(nums, k)}")
print(f"{k}th smallest element is {find_kth_smallest(nums, k)}")

○ simple problems and solutions using the above algorithms

○ solutions for some of the problems given in hacker rank test etc

10. Recursion

Recursion in Python refers to the process in which a function calls itself in order to solve a
problem. This technique is often used to break a problem into smaller, more manageable
subproblems. A recursive function typically has two parts:

1.​ Base Case: A condition that stops the recursion when it's met.
2.​ Recursive Case: The part where the function calls itself with modified parameters.

Task 1
You are working on a program for a clothing store. Each item has multiple size and color
options. Write a recursive function to generate all possible combinations (subsets) of items
in a shopping cart.
def generate_combinations(cart, index=0, current_combination=None):
if current_combination is None:
current_combination = []

# Base case: If we've processed all items in the cart

if index == len(cart):
return [current_combination]
 # Recursive case:
# 1. Exclude the current item from the combination
without_current = generate_combinations(cart, index + 1, current_combination)

# 2. Include the current item in the combination

with_current = generate_combinations(cart, index + 1, current_combination + [cart[index]])

# Return the union of both cases

return without_current + with_current

# Example usage:
shopping_cart = ["T-shirt", "Jeans", "Jacket"]
combinations = generate_combinations(shopping_cart)

# Print all possible combinations

for combination in combinations:
print(combination)

Task 2:
A company has a hierarchy where each employee has subordinates. Each subordinate can
also have their own subordinates, forming a tree structure. Bonuses are calculated as the
sum of an employee's direct bonus and all their subordinates' bonuses. Write a recursive
function to calculate the total bonus for any given employee.
class Employee:
def __init__(self, name, direct_bonus):
[Link] = name
self.direct_bonus = direct_bonus
[Link] = []

def calculate_total_bonus(employee):
# Base case: if the employee has no subordinates
 if not [Link]:
return employee.direct_bonus

# Recursive case: calculate bonus for all subordinates

total_bonus = employee.direct_bonus
for subordinate in [Link]:
total_bonus += calculate_total_bonus(subordinate)

return total_bonus

# Example usage:
# Constructing a sample hierarchy
ceo = Employee("Alice", 10000)
cto = Employee("Bob", 8000)
dev_manager = Employee("Charlie", 6000)
dev1 = Employee("David", 4000)
dev2 = Employee("Eve", 3500)

# Assigning subordinates
[Link] = [cto]
[Link] = [dev_manager]
dev_manager.subordinates = [dev1, dev2]

# Calculate total bonus for the CEO

total_bonus_ceo = calculate_total_bonus(ceo)
print(f"Total bonus for CEO {[Link]}: {total_bonus_ceo}")

Task 3:
You are building a word-suggestion tool for a text editor. Write a recursive function to
generate all possible permutations of the letters in a word to help in identifying potential
typos or suggestions.
def generate_permutations(word):
# Base case: if the word has only one letter, return it as the only permutation
if len(word) == 1:
return [word]

# Recursive case: generate permutations for the rest of the word

permutations = []
for i, letter in enumerate(word):
# Extract the current letter and the remaining letters
remaining_letters = word[:i] + word[i+1:]

# Generate all permutations for the remaining letters

for sub_permutation in generate_permutations(remaining_letters):
# Append the current letter to the permutations of the remaining letters
[Link](letter + sub_permutation)

return permutations

# Example usage
word = "abc"
all_permutations = generate_permutations(word)
print(f"All permutations of '{word}': {all_permutations}")

Task 4:
A person can climb a staircase by taking 1 step, 2 steps, or 3 steps at a time. Write a
recursive function to calculate how many distinct ways there are to climb a staircase with n
steps.
def count_ways(n):
"""
Recursive function to count the number of distinct ways to climb a staircase.
 :param n: Total number of steps in the staircase
:return: Number of distinct ways to climb the staircase
"""
# Base cases
if n == 0:
return 1 # One way: do nothing
if n < 0:
return 0 # No way to climb negative steps

# Recursive case: Sum the ways to climb (n-1), (n-2), and (n-3) steps
return count_ways(n - 1) + count_ways(n - 2) + count_ways(n - 3)

# Example usage
n=5
print(f"Number of ways to climb {n} steps: {count_ways(n)}")

Task 5:
You are building a code editor and need to check if a string of parentheses (e.g.,
"(()())") is balanced. Write a recursive function to determine if the parentheses in a
string are properly matched.
def is_balanced(s, index=0, count=0):
"""
Recursive function to check if the parentheses in a string are balanced.

:param s: The string containing parentheses

:param index: The current index being checked
:param count: The current count of open parentheses
:return: True if the string is balanced, False otherwise
"""
# Base case: If we've checked all characters
if index == len(s):
 return count == 0 # Balanced if no unmatched open parentheses remain

# If it's an open parenthesis, increment the count

if s[index] == '(':
return is_balanced(s, index + 1, count + 1)

# If it's a close parenthesis, decrement the count

if s[index] == ')':
if count == 0:
return False # More close parentheses than open ones
return is_balanced(s, index + 1, count - 1)

# If the character is neither '(' nor ')', just move to the next character
return is_balanced(s, index + 1, count)

# Example usage
parentheses_string = "(()())"
print(f"Is the string '{parentheses_string}' balanced? {is_balanced(parentheses_string)}")

11. Brute Force Algorithm

Brute force in Python refers to a straightforward approach to solving a problem by trying all
possible solutions or combinations without using any optimization techniques. This method
typically involves exhaustive searching or trial-and-error, where every possible option is checked
until the correct solution is found. Although brute force methods are often simple to implement,
they can be inefficient, especially for large datasets or complex problems.
Task 1: Finding the Maximum Subarray Sum

def max_subarray_sum(arr):

max_sum = float('-inf')

for i in range(len(arr)):
 for j in range(i, len(arr)):

current_sum = sum(arr[i:j+1])

max_sum = max(max_sum, current_sum)

return max_sum

# Example usage

arr = [1, -2, 3, 4, -1, 2]

print(max_subarray_sum(arr)) # Output: 8 (subarray [3, 4, -1, 2])

Task 2: Finding All Pairs with a Specific Sum

def find_pairs_with_sum(arr, target):

pairs = []

for i in range(len(arr)):

for j in range(i+1, len(arr)):

if arr[i] + arr[j] == target:

[Link]((arr[i], arr[j]))

return pairs

# Example usage

arr = [1, 2, 3, 4, 5]

target = 5

print(find_pairs_with_sum(arr, target)) # Output: [(1, 4), (2, 3)]

Task 3: Brute Force Approach to Find the First Duplicate in an Array

def first_duplicate(arr):

for i in range(len(arr)):

for j in range(i + 1, len(arr)):

if arr[i] == arr[j]:

return arr[i]

return -1 # No duplicates found

# Example usage

arr = [1, 2, 3, 4, 2, 5]

print(first_duplicate(arr)) # Output: 2

Task 4: Brute Force Approach to Find the Longest Common Substring

def longest_common_substring(str1, str2):

longest_substr = ""

for i in range(len(str1)):

for j in range(len(str2)):

temp = ""

while i + len(temp) < len(str1) and j + len(temp) < len(str2) and str1[i + len(temp)] ==
str2[j + len(temp)]:

temp += str1[i + len(temp)]

if len(temp) > len(longest_substr):

 longest_substr = temp

return longest_substr

# Example usage

str1 = "abcdef"

str2 = "zcdemf"

print(longest_common_substring(str1, str2)) # Output: "cd"

Task 5: Brute Force Approach to Find All Triplets That Sum to Zero

def find_triplets(arr):

triplets = []

n = len(arr)

for i in range(n):

for j in range(i + 1, n):

for k in range(j + 1, n):

if arr[i] + arr[j] + arr[k] == 0:

[Link]([arr[i], arr[j], arr[k]])

return triplets

# Example usage

arr = [-1, 0, 1, 2, -1, -4]

print(find_triplets(arr)) # Output: [[-1, -1, 2], [-1, 0, 1]]

12. Backtracking

Backtracking in Python is a problem-solving technique used to find all (or some) solutions to
problems by exploring all potential candidates and eliminating those that fail to meet the criteria.
The key idea behind backtracking is to build a solution incrementally and, when a solution path
is determined to be invalid or unsatisfactory, undo the last step (backtrack) and try a different
path.

Backtracking is often used for problems involving combinations, permutations, and constraint
satisfaction problems, such as puzzles, games, and optimization problems.

Steps in Backtracking:

1.​ Choose: Make a choice and move forward.

2.​ Explore: Recursively explore further choices.
3.​ Backtrack: If the current path leads to an invalid solution, undo the last choice and try
another.

Task 1: Subset Sum Problem

def find_subsets(nums, target):
def backtrack(start, target, current_subset):
# If target is 0, we have found a valid subset
if target == 0:
[Link](current_subset[:])
return
if target < 0:
return # No valid subset can be formed

for i in range(start, len(nums)):

# Include the current number and explore further
current_subset.append(nums[i])
 backtrack(i + 1, target - nums[i], current_subset)
# Backtrack, remove the number and explore other possibilities
current_subset.pop()

subsets = []
[Link]() # Optional: helps in optimization by stopping early for larger numbers
backtrack(0, target, [])
return subsets

# Example usage:
nums = [2, 3, 5, 8, 2, 1]
target = 8
result = find_subsets(nums, target)
print(result)

Task 2: Generate Parentheses

def generate_parentheses(n):
def backtrack(current_combination, open_count, close_count):
# If the current combination is of length 2*n, it's a valid combination
if len(current_combination) == 2 * n:
[Link](current_combination)
return

# If we can add an open parenthesis, do it and recurse

if open_count < n:
backtrack(current_combination + '(', open_count + 1, close_count)

# If we can add a close parenthesis, do it and recurse

if close_count < open_count:
backtrack(current_combination + ')', open_count, close_count + 1)
 combinations = []
backtrack('', 0, 0)
return combinations

# Example usage:
n=3
result = generate_parentheses(n)
print(result)

Task 3: Letter Case Permutation

def letter_case_permutations(s):
def backtrack(index, current_combination):
# If we've reached the end of the string, add the current combination to the result
if index == len(s):
[Link](''.join(current_combination))
return

# If the current character is a letter, try both lowercase and uppercase

if s[index].isalpha():
current_combination.append(s[index].lower())
backtrack(index + 1, current_combination)
current_combination.pop() # Backtrack

current_combination.append(s[index].upper())
backtrack(index + 1, current_combination)
current_combination.pop() # Backtrack
else:
# If it's not a letter, just add it as is
current_combination.append(s[index])
backtrack(index + 1, current_combination)
current_combination.pop() # Backtrack
 permutations = []
backtrack(0, [])
return permutations

# Example usage:
input_str = "a1b2"
result = letter_case_permutations(input_str)
print(result)

13. Dynamic Programming

Dynamic programming (DP) in Python is a problem-solving technique used to solve complex

problems by breaking them down into simpler subproblems and storing the solutions to those
subproblems to avoid redundant work. The core idea is to solve each subproblem just once and
store the result, making it available for subsequent subproblems. This reduces the time
complexity compared to naive recursion by ensuring that each subproblem is solved only once.

Key Concepts in Dynamic Programming:

1.​ Optimal Substructure: The problem can be broken down into smaller subproblems,
which can be solved independently. The optimal solution to the overall problem can be
constructed from the optimal solutions to these subproblems.
2.​ Overlapping Subproblems: The problem involves solving the same subproblems
multiple times. By storing the results of subproblems, we can avoid recalculating the
same values.

Types of Dynamic Programming:

 ●​ Top-Down Approach (Memoization): This approach involves solving the problem
using recursion and storing the results of subproblems in a cache (memoization) to avoid
recomputation.
●​ Bottom-Up Approach (Tabulation): This approach builds the solution iteratively from
the smallest subproblems to the largest one, storing results in a table.

Task 1: Fibonacci Series

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

# Initialize an array to store Fibonacci numbers

fib = [0] * (n + 1)

# Base cases
fib[0] = 0
fib[1] = 1

# Compute Fibonacci numbers from 2 to n

for i in range(2, n + 1):
fib[i] = fib[i - 1] + fib[i - 2]

return fib[n]

# Example usage:
n = 10
print(f"The {n}th Fibonacci number is: {fibonacci(n)}")

Task 2: Minimum Coins

def min_coins(coins, amount):
# Initialize a list to store the minimum number of coins for each amount
 dp = [float('inf')] * (amount + 1)
# Initialize a list to store the last coin used to make up the amount
last_coin = [-1] * (amount + 1)

# Base case: No coins are needed to make amount 0

dp[0] = 0

# Loop through all amounts from 1 to the target amount

for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0 and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
last_coin[i] = coin

# If dp[amount] is still infinity, it means the amount cannot be formed

if dp[amount] == float('inf'):
return -1, []

# Reconstruct the coins used by tracing the last_coin array

result_coins = []
while amount > 0:
result_coins.append(last_coin[amount])
amount -= last_coin[amount]

# Return the minimum number of coins and the list of coins used
return dp[-1], result_coins

# Example usage:
coins = [1, 2, 5]
amount = 8
min_coins_needed, coins_used = min_coins(coins, amount)
print(f"Minimum coins needed: {min_coins_needed}")
print(f"Coins used: {coins_used}")

Task 3:
A thief is robbing houses along a street. Each house has a certain amount of money, but if
the thief robs two adjacent houses, the police will catch him. Write a function to find the
maximum amount of money the thief can rob.
def rob(nums):
# If there are no houses, the thief can't rob anything
if not nums:
return 0

# If there is only one house, rob that house

if len(nums) == 1:
return nums[0]

# Initialize the DP array

dp = [0] * len(nums)

# Base cases
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

# Fill the DP array using the recurrence relation

for i in range(2, len(nums)):
dp[i] = max(dp[i-1], nums[i] + dp[i-2])

# The result is in the last element of the DP array

return dp[-1]

# Example usage
houses = [2, 7, 9, 3, 1]
print(rob(houses)) # Output: 12 (Rob houses 1, 3, and 5)

Task 4: Climbing Stairs

You are climbing a staircase with n steps. Each time you can either climb 1 or 2 steps. Write a
function to determine how many ways you can reach the top.
def climbStairs(n):
# Base cases
if n == 1:
return 1
if n == 2:
return 2

# Initialize the first two values

first = 1
second = 2

# Calculate the number of ways iteratively

for i in range(3, n + 1):
current = first + second
first = second
second = current

return second

# Example usage
n=5
print(climbStairs(n)) # Output: 8

Task 5: Stock Max

You are given an array where each element represents the price of a stock on a given day. Write a
function to find the maximum profit you can achieve by buying and selling the stock once.
def maxProfit(prices):
# If the list is empty or has only one price, no profit can be made
if not prices or len(prices) == 1:
return 0

# Initialize the minimum price to a very high value and the max profit to 0
min_price = float('inf')
max_profit = 0

# Loop through the prices

for price in prices:
# Update the minimum price encountered so far
min_price = min(min_price, price)

# Calculate the potential profit by selling at the current price

profit = price - min_price

# Update the maximum profit if the current profit is greater

max_profit = max(max_profit, profit)

return max_profit

# Example usage
prices = [7, 1, 5, 3, 6, 4]
print(maxProfit(prices)) # Output: 5 (Buy at 1, sell at 6)

Task 6: Perfect Square

Given a positive integer n, write a function to return the least number of perfect square numbers
whose sum is equal to n
import math

def numSquares(n):
# Create a DP array with large initial values
dp = [float('inf')] * (n + 1)
# Create an array to store the perfect square numbers used to get the sum
square_used = [-1] * (n + 1)

# Base case: 0 can be made with 0 perfect squares

dp[0] = 0

# Loop through all numbers from 1 to n

for i in range(1, n + 1):
j=1
while j * j <= i:
if dp[i - j * j] + 1 < dp[i]:
dp[i] = dp[i - j * j] + 1
square_used[i] = j * j
j += 1

# Backtrack to find the perfect squares used

result = []
while n > 0:
[Link](square_used[n])
n -= square_used[n]

return dp[-1], result # Return both the minimum number of squares and the list of squares
used

# Example usage
n = 12
min_squares, squares = numSquares(n)
print(f"Minimum number of perfect squares: {min_squares}") # Output: 3
print(f"Perfect squares used: {squares}") # Output: [4, 4, 4]

Task 7: Longest Substring

def lengthOfLongestSubstring(s):
# Set to store characters in the current window
char_set = set()

# Initialize pointers and variables to track the result

start = 0
max_length = 0
longest_start = 0 # To store the starting index of the longest substring

# Iterate over the string using the `end` pointer

for end in range(len(s)):
# If the character is already in the set, move `start` to remove the duplicate
while s[end] in char_set:
char_set.remove(s[start])
start += 1

# Add the current character to the set

char_set.add(s[end])

# Update the max_length and longest_start when a new longest substring is found
if end - start + 1 > max_length:
max_length = end - start + 1
longest_start = start

# Extract the longest substring using the recorded starting index and length
longest_substring = s[longest_start:longest_start + max_length]
 return max_length, longest_substring

# Example usage
s = "abcabcbbdefabzzz"
length, substring = lengthOfLongestSubstring(s)
print(f"Length of longest substring: {length}") # Output: 3
print(f"Longest substring: {substring}") # Output: "abc"

14. Greedy Algorithms

A greedy algorithm in Python is a problem-solving technique that follows a simple, intuitive

approach: at each step, it makes the locally optimal choice with the hope that these local choices
will lead to a globally optimal solution. In other words, the greedy algorithm chooses the best
option available at the current step without considering the broader problem or future
consequences.

Greedy algorithms are typically used for optimization problems, where the goal is to find the best
solution among a set of feasible solutions.

Key Characteristics of Greedy Algorithms:

1.​ Greedy Choice Property: A globally optimal solution can be arrived at by selecting a
locally optimal solution at each step.
2.​ Optimal Substructure: The problem can be broken down into smaller subproblems that
are solved independently and can be combined to form the solution to the larger problem.

However, greedy algorithms do not always produce the optimal solution for every problem. They
work well for problems where making a locally optimal choice leads to the global optimal
solution, such as certain graph and optimization problems.

Example: Coin Change Problem (Greedy Approach)

Suppose you are given a set of coin denominations and a target amount. The goal is to find the
minimum number of coins needed to make up that target amount. A greedy algorithm would
always pick the largest coin denomination first and then continue with the remaining amount.

Task 1: Job Scheduling

# Function to schedule jobs for maximum profit
def job_scheduling(jobs, n):
# Sort jobs in descending order of profit
[Link](key=lambda x: x[2], reverse=True)

# Array to keep track of free time slots

result = [-1] * n # Initially all time slots are free
total_profit = 0

# Iterate through all jobs

for job in jobs:
job_id, deadline, profit = job

# Find a free slot for this job (starting from the last possible time slot)
for j in range(min(n - 1, deadline - 1), -1, -1):
if result[j] == -1: # Slot is free
result[j] = job_id # Assign job to this slot
total_profit += profit
break

return total_profit, result

# Example usage
if __name__ == "__main__":
# List of jobs with (id, deadline, profit)
jobs = [
('A', 4, 20),
 ('B', 1, 10),
('C', 1, 40),
('D', 1, 30)
]

n = len(jobs)
total_profit, result = job_scheduling(jobs, n)

print(f"Total Profit: {total_profit}")

print(f"Jobs scheduled in time slots: {result}")

Task 2: Max Sum of Non-adjacent Numbers

def max_sum_non_adjacent(arr):
incl = 0 # Maximum sum including the previous element
excl = 0 # Maximum sum excluding the previous element

for num in arr:

# Current max excluding the previous element (this is the previous 'excl' max)
new_excl = max(incl, excl)

# Current max including the current element

incl = excl + num

# Update excl to be the previous 'new_excl'

excl = new_excl

# The result is the maximum of incl and excl

return max(incl, excl)

# Example usage
if __name__ == "__main__":
 arr = [3, 2, 5, 10, 7]
result = max_sum_non_adjacent(arr)
print(f"Maximum sum of non-adjacent elements: {result}")

Task 3: Candies

You have a set of children with ratings. You need to give candies to the children such that:

●​ Each child gets at least one candy.

●​ Children with higher ratings get more candies than their neighbors. Find the minimum
number of candies to distribute.

def minCandies(ratings):
# If ratings list is empty, no candies needed
if not ratings:
return 0

n = len(ratings)

# Initialize a list to store the number of candies each child will get
candies = [1] * n

# First pass: Traverse from left to right

for i in range(1, n):
# If current child's rating is higher than the previous, give one more candy
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1

# Second pass: Traverse from right to left

for i in range(n - 2, -1, -1):
# If current child's rating is higher than the next, ensure they get more candies
 if ratings[i] > ratings[i + 1]:
# Ensure we are giving at least one more candy than the right neighbor
candies[i] = max(candies[i], candies[i + 1] + 1)

# Return the sum of the candies list, which gives the total number of candies needed
return sum(candies)

# Example usage
ratings = [1, 0, 2] # Example input
print(minCandies(ratings)) # Output: 5

Task 4: Toys
You are given an array of integers representing the prices of toys. You also have a budget. Find
the maximum number of toys you can buy with the given budget by selecting the cheapest toys
first.
def maximum_toys(prices, budget):
# Sort prices in ascending order to buy the cheapest toys first
[Link]()

# Initialize variables to track number of toys and current budget

num_toys = 0
total_cost = 0

# Iterate over the sorted prices and keep adding toys until the budget is exhausted
for price in prices:
if total_cost + price <= budget:
total_cost += price
num_toys += 1
 else:
break # Stop if adding the next toy exceeds the budget

return num_toys

# Example usage
if __name__ == "__main__":
prices = [1, 12, 5, 111, 200, 1000, 10]
budget = 50
result = maximum_toys(prices, budget)
print(f"Maximum number of toys that can be bought: {result}")

Task 5: Train
Given the arrival and departure times of trains at a station, find the minimum number of
platforms required so that no train has to wait.
def min_platforms(arrivals, departures):
# Sort the arrival and departure times
[Link]()
[Link]()

# Initialize pointers and variables

i = 0 # Pointer for arrival times
j = 0 # Pointer for departure times
platforms_needed = 0
max_platforms = 0

# Process each train

while i < len(arrivals):
# If a train arrives before the last one departs, we need a new platform
 if arrivals[i] <= departures[j]:
platforms_needed += 1
i += 1 # Move to the next arrival
else:
platforms_needed -= 1
j += 1 # Move to the next departure

# Update the maximum platforms needed

max_platforms = max(max_platforms, platforms_needed)

return max_platforms

# Example usage
if __name__ == "__main__":
arrivals = [100, 150, 200, 300, 350]
departures = [120, 180, 210, 330, 400]
result = min_platforms(arrivals, departures)
print(f"Minimum number of platforms required: {result}")

15. Problems based on Recursion, Brute Force algorithm, dynamic

programming, greedy algorithm. - DONE

Two Pointer Approach

The two-pointer approach is a technique used to solve problems involving sequences or arrays
in Python. It involves using two pointers, typically represented as indices, to traverse the
sequence from different directions or to compare elements in some way. The two pointers can
move towards each other, away from each other, or in the same direction, depending on the
specific problem.
The idea is to reduce the time complexity of the problem by efficiently narrowing down the
search space or finding the desired pair of elements. This approach is often applied to problems
like searching for pairs or subarrays, sorting, and partitioning.

Task 1: Two Sums

def two_sum(nums, target):
left, right = 0, len(nums) - 1 # Initialize pointers at the start and end of the array
while left < right:
current_sum = nums[left] + nums[right]

if current_sum == target:
return [nums[left], nums[right]]
elif current_sum < target:
left += 1 # Move the left pointer to the right
else:
right -= 1 # Move the right pointer to the left

return None # Return None if no pair is found

# Example usage
nums = [1, 2, 3, 4, 5, 6]
target = 10
result = two_sum(nums, target)
print(f"Pair with target sum {target}: {result}")

Task 2: Reversing an Array

def reverse_array(arr):
left, right = 0, len(arr) - 1 # Pointers at the start and end of the array
while left < right:
arr[left], arr[right] = arr[right], arr[left] # Swap the elements
left += 1
right -= 1
 return arr

# Example usage
arr = [1, 2, 3, 4, 5]
reversed_arr = reverse_array(arr)
print(f"Reversed array: {reversed_arr}")

Task 3: Remove Duplicates

def remove_duplicates(nums):
if not nums:
return 0
left = 0
for right in range(1, len(nums)):
if nums[right] != nums[left]:
left += 1
nums[left] = nums[right]
return left + 1

# Example usage
nums = [1, 1, 2, 2, 3, 3, 4]
new_length = remove_duplicates(nums)
print(f"Array after removing duplicates: {nums[:new_length]}")

Task 4: Partition Odd and Even

def partition_even_odd(nums):
left, right = 0, len(nums) - 1 # Pointers at the start and end of the array
while left < right:
print(nums)
if nums[left] % 2 == 0: # Even number, move left pointer
left += 1
elif nums[right] % 2 != 0: # Odd number, move right pointer
 right -= 1
else:
nums[left], nums[right] = nums[right], nums[left] # Swap even and odd numbers
left += 1
right -= 1
return nums

# Example usage
nums = [1, 2, 3, 4, 5, 6, 7, 10]
result = partition_even_odd(nums)
print(f"Array after partitioning even and odd numbers: {result}")

Task 5: Maximum Product

def max_product(nums):
left, right = 0, len(nums) - 1 # Pointers at the start and end of the array
max_product = float('-inf') # Initialize with a very small value

while left < right:

current_product = nums[left] * nums[right]
max_product = max(max_product, current_product)

# Move pointers to find the maximum product

if nums[left] < nums[right]:
left += 1
else:
right -= 1

return max_product

# Example usage
nums = [-10, -5, 0, 2, 5, 7]
result = max_product(nums)
print(f"Maximum product of two elements: {result}")

Sliding Window Approach

A sliding window in Python refers to a technique used to solve problems that involve examining
a contiguous subarray or subsequence within a larger array or sequence. The idea is to maintain a
window of fixed or variable size that "slides" over the array or sequence to analyze different
segments without needing to recheck elements repeatedly.

The sliding window technique is particularly useful for problems involving:

●​ Finding the maximum or minimum sum of subarrays of a fixed size.

●​ Finding subarrays that satisfy certain conditions.
●​ Optimizing time complexity, especially for problems that would otherwise require nested
loops.

Example:

For a problem like finding the maximum sum of a subarray of size k, the sliding window
approach can be applied to avoid recalculating the sum from scratch for each subarray:

def max_sum_subarray(arr, k):

n = len(arr)
if n < k:
return None

# Compute the sum of the first window

window_sum = sum(arr[:k])
max_sum = window_sum

# Slide the window over the array

 for i in range(k, n):
window_sum += arr[i] - arr[i - k] # Add the next
element, remove the first element of the previous window
max_sum = max(max_sum, window_sum)

return max_sum

In this example, the window slides by adding the next element and removing the first element
from the previous window, ensuring efficient computation without recalculating the entire sum
each time.

Task 1: Maximum Subarray

def max_sum_subarray(arr, k):
n = len(arr)
if n < k:
return None

# Compute the sum of the first window

window_sum = sum(arr[:k])
max_sum = window_sum

# Slide the window

for i in range(k, n):
window_sum += arr[i] - arr[i - k] # Add the new element, remove the old one
max_sum = max(max_sum, window_sum)

return max_sum

# Example usage:
arr = [2, 1, 5, 1, 3, 2]
k=3
print("Maximum sum of subarray of size", k, "is:", max_sum_subarray(arr, k))

Task 2: Longest Substring without repeating characters

def longest_unique_substring(s):
left = 0
max_len = 0
char_index_map = {}

for right in range(len(s)):

if s[right] in char_index_map:
left = max(left, char_index_map[s[right]] + 1) # Move the left pointer to avoid duplicates
char_index_map[s[right]] = right
max_len = max(max_len, right - left + 1)

return max_len

# Example usage:
s = "abcabcbb"
print("Longest substring without repeating characters is:", longest_unique_substring(s))