Tag: Python

Categories
Coding Computer Science Python

Solving Problem: Sum of Multiples

Software developer programming code black by Markus Spiske is licensed under CC-CC0 1.0

Introduction

The sum of multiples of k below n is:

Formula:

Sk=k⋅m(m+1)2

where m=⌊n−1k⌋.

Problem Statement:

Find the sum of multiples of 3 or 5 below N.

For example:

If we list all the natural numbers below that are multiples of  3 or 5, we get 3, 5, 6, and 9. The sum of these multiples is 23.

Input Format

The first line contains  T, which denotes the number of test cases. This is followed by T lines, each containing an integer, N.

Constraints

  • 1 <= T <= 10^5
  • 1 <= N <= 10^9

Output Format

For each test case, print an integer denoting the sum of all the multiples of 3 or 5 below N.

Sample Input 0

2
10
100

Sample Output 0

23
2318

Explanation 0

For if we list all the natural numbers below 10 that are multiples of  3 or 5, we get 3, 5, 6, and 9. The sum of these multiples is 23.

Similarly, for N=100, we get 2318.

Solution:

sum_of_multiples.py
Python
#!/bin/python3
import sys
t = int(input().strip())
if 1 <= t <= pow(10,5):
    def sum_of_multiples(k, limit):
        m = (limit - 1) // k
        return k * m * (m+1) // 2
        
    for a0 in range(t):
        n = int(input().strip())
        s3 = sum_of_multiples(3, n)
        s5 = sum_of_multiples(5, n)
        s15 = sum_of_multiples(15, n)
        
        total = s3 + s5 - s15
        print(total)

Output:

Input (stdin)

  • 2
  • 10
  • 100

Your Output (stdout)

  • 23
  • 2318

Expected Output

  • 23
  • 2318

Note:

Avoid using loops when solving this problem, as N can be large enough (about 10^9), which can cause time and space to explode. The trick is to use arithmetic series formulas.

sum_of_multiples1.py
Python
import sys
t = int(input().strip())
if 1 <= t <= pow(10,5):
    for a0 in range(t):
        n = int(input().strip())
        total = 0
        # print("n = ", n)
        if 1 <= n <= pow(10,9):
            if n == 1:
                total = n
            li = [i for i in range(1, n) if (i%3 == 0 or i%5 == 0)]
            total = sum(li)
            print(total)

The above code has O(n) complexity; however, it fails under memory constraints. When used with the arithmetic formula, the time complexity becomes O(1).

Reference:

Contests | HackerRank

Categories
Coding Computer Science Python

Solving Problem: Combinations

Binary source code by Markus Spiske is licensed under CC-CC0 1.0

(Python)

Problem Statement:

You are given a string S.
Your task is to print all possible combinations, up to size, of the string in lexicographically sorted order.

Input Format

A single line containing the string and integer value separated by a space.

Constraints

0 < k <= len(S)


The string contains only UPPERCASE characters.

Output Format

Print the different combinations of the string on separate lines.

Sample Input

HACK 2

Sample Output

A
C
H
K
AC
AH
AK
CH
CK
HK

Solution:

combinations.py
Python
from itertools import combinations
# Input from user
inp = input().split()
S = inp[0]
k = int(inp[1])
li1 = []
# Create a list with combinations
for i in range(1, k+1):
    li1.extend(list(combinations(S, i)))
# Sort the list lexicographically
for i in range(0, len(li1)):
    li1[i] = str(''.join(sorted(list(li1[i]))))
li1 = sorted(li1, key=lambda s: (len(s), s.lower())) # sort the list alphabetically ascending
# print the string
for i in range(0, len(li1)):
    print(li1[i])

Output:

Reference:

itertools.combinations() | HackerRank

Categories
Computer Science

Solving Problem: Trigonometry

(Python)

Problem Statement:

 ABC is a right triangle,  90° at  B.
Therefore,  ∠ ABC = 90.

Point  M is the midpoint of the hypotenuse.

You are given the lengths AB and BC.
Your task is to find ∠MBC (angle θ, as shown in the figure) in degrees.

Input Format

The first line contains the length of side AB.
The second line contains the length of the side BC.

Constraints

  • 0 < AB <= 100
  • 0 < BC <= 100
  • Lengths  AB and  BC are natural numbers.

Output Format

Output  ∠MBC in degrees.

Note: Round the angle to the nearest integer.

Examples:
If the angle is 56.5000001°, then output 57°.
If the angle is 56.5000000°, then output 57°.
If the angle is 56.4999999°, then output 56°.

0° < θ° < 90°

Sample Input

10
10

Sample Output

45°

Solution:

Python
# Enter your code here. Read input from STDIN. Print output to STDOUT
import math
AB = int(input())
BC = int(input())
Angle_ABC = 90
AC = pow(AB^2+BC^2, 1/2)
theta = round(math.degrees(math.atan(AB/BC)))
#print(f"{theta}\u00B0")
print(str(theta)+chr(176))

Output:

Note:

a + b + c = 180
ac = sqrt(a^2 + b^2)
ma = mb = mc – midpoint theorem
theta = mbc
mcb = mbc – midpoint theorem
sin(theta) = ab/ac
cos(theta) = bc/ac
tan(theta) = ab/bc
theta = arctan(ab/bc)

arctan is the inverse tangent of a given angle.

You can use numpy arctan or math atan.

Refer:

numpy.arctan2 — NumPy v2.4 Manual

math — Mathematical functions — Python 3.14.4 documentation

Reference:

Find Angle MBC | HackerRank

Categories
Computer Science

Bit Manipulation Basics

(Python)

Let’s have a quick review of Bit Manipulation techniques in Python.

Bitwise Operators

OperatorDescriptionExample
&Bitwise ANDa & b
`Bitwise ORa ` b
^Bitwise XORa ^ b
~Bitwise NOT~a
<<Left Shifta << n
>>Right Shifta >> n

Example Program

Python
# Bit manipulation demo in Python
def bit_operations(a: int, b: int):
    """Perform common bitwise operations on two integers."""
    try:
        # Ensure inputs are integers
        if not isinstance(a, int) or not isinstance(b, int):
            raise ValueError("Both inputs must be integers.")
        print(f"a = {a} ({bin(a)})")
        print(f"b = {b} ({bin(b)})\n")
        # AND
        print(f"a & b  = {a & b} ({bin(a & b)})")
        # OR
        print(f"a | b  = {a | b} ({bin(a | b)})")
        # XOR
        print(f"a ^ b  = {a ^ b} ({bin(a ^ b)})")
        # NOT
        print(f"~a     = {~a} ({bin(~a)})")
        print(f"~b     = {~b} ({bin(~b)})")
        # Left shift
        print(f"a << 2 = {a << 2} ({bin(a << 2)})")
        # Right shift
        print(f"a >> 2 = {a >> 2} ({bin(a >> 2)})")
    except ValueError as e:
        print(f"Error: {e}")
# Example usage
if __name__ == "__main__":
    bit_operations(7, 3)  # 7 = 0b111, 3 = 0b011

Output:

a = 7 (0b111)
b = 3 (0b11)

a & b = 3 (0b11)
a | b = 7 (0b111)
a ^ b = 4 (0b100)
~a = -8 (-0b1000)
~b = -4 (-0b100)
a << 2 = 28 (0b11100)

Bit Manipulation Tricks

Python
# Check if the k-th bit is set (0-indexed from right)
def is_kth_bit_set(n, k):
    return (n & (1 << k)) != 0
# Set the k-th bit
def set_kth_bit(n, k):
    return n | (1 << k)
# Clear the k-th bit
def clear_kth_bit(n, k):
    return n & ~(1 << k)
# Toggle the k-th bit
def toggle_kth_bit(n, k):
    return n ^ (1 << k)
# Count set bits (Brian Kernighan’s Algorithm)
def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count
n = 13
k = 2
print(f"n = {n} Binary n: ", bin(n))
print(f"k = {k} Binary k: ", bin(k))
print("Is 'k'th bit set? ", is_kth_bit_set(n,k))
print("n after setting 'k'th bit: ", set_kth_bit(n,k), f"Binary n = ({bin(n)})")
print("n after clear 'k'th bit: ", clear_kth_bit(n,k), f"Binary n = ({bin(n)})")
print("n after toggle 'k'th bit: ", toggle_kth_bit(n,k), f"Binary n = ({bin(n)})")
print("Set bits in n: ", count_set_bits(n))

Output:

n = 13 Binary n: 0b1101
k = 2 Binary k: 0b10
Is ‘k’th bit set? True
n after setting ‘k’th bit: 13 Binary n = (0b1101)
n after clear ‘k’th bit: 9 Binary n = (0b1101)
n after toggle ‘k’th bit: 9 Binary n = (0b1101)
Set bits in n: 3

Categories
Computer Science

Object Oriented Programming – Polymorphism 

What is Polymorphism?

Polymorphism means “many forms”.
In OOP, it allows the same method name (or operator) to behave differently depending on the object or data type it is acting upon.

It helps in:

  • Code reusability
  • Flexibility
  • Maintainability

Types of Polymorphism in Python

Python mainly supports runtime polymorphism (method overriding) and compile-time-like polymorphism (method overloading via default arguments or *args).

1. Polymorphism with Functions and Objects

A single function can work with different types of objects.

Python
# Example: Same function name, different object types
class Dog:
    def speak(self):
        return "Woof!"
class Cat:
    def speak(self):
        return "Meow!"
def animal_sound(animal):
    print(animal.speak())
# Using polymorphism
dog = Dog()
cat = Cat()
animal_sound(dog)  # Woof!
animal_sound(cat)  # Meow!

Here, animal_sound() works with any object that has a .speak() method — this is duck typing in Python.

2. Polymorphism with Inheritance (Method Overriding)

Child classes can override methods from the parent class.

Python
class Bird:
    def fly(self):
        return "Some birds can fly."
class Sparrow(Bird):
    def fly(self):
        return "Sparrow flies high."
class Penguin(Bird):
    def fly(self):
        return "Penguins can't fly."
# Runtime polymorphism
for bird in [Sparrow(), Penguin()]:
    print(bird.fly())

Output:

Sparrow flies high.
Penguins can't fly.

3. Polymorphism with Built-in Functions

Many built-in functions in Python are polymorphic.

Python
print(len("Hello"))     # Works on string → 5
print(len([1, 2, 3]))   # Works on list → 3

4. Operator Overloading (Special Methods)

Operators like +, *, etc., behave differently for different data types.

print(5 + 10)       # Integer addition → 15
print("Hi " + "Py") # String concatenation → Hi Py

You can define custom behavior using magic methods:

Python
class Book:
    def __init__(self, pages):
        self.pages = pages
    def __add__(self, other):
        return self.pages + other.pages
b1 = Book(100)
b2 = Book(200)
print(b1 + b2)  # 300

Sure! Let’s break down polymorphism in Python in the context of Object-Oriented Programming (OOP).

Key Takeaways

  • Polymorphism lets the same interface work for different data types or classes.
  • In Python, it’s often achieved through method overriding, duck typing, and operator overloading.
  • It improves code flexibility and reduces duplication.

If you want, I can prepare a single Python program that demonstrates all types of polymorphism in one place for easy learning.
Do you want me to create that?

Categories
Computer Science

Object Oriented Programming – Inheritance

What is Inheritance?

Inheritance is a fundamental concept in object-oriented programming (OOP) that allows a class to inherit attributes and methods from another class. This promotes code reusability and establishes a hierarchical relationship between classes.

Basic Syntax and Example

In Python, inheritance is implemented by defining a new class that derives from an existing class. The derived class (child class) inherits the attributes and methods of the base class (parent class). Here is a basic example:

Python
# Parent class
class Person:
   def __init__(self, name, id):
       self.name = name
       self.id = id
   def display(self):
       print(self.name, self.id)
# Child class
class Employee(Person):
   def print_emp(self):
       print("Employee class called")
# Creating an object of the child class
emp = Employee("John", 101)
emp.display() # Calling parent class method
emp.print_emp() # Calling child class method

In this example, the Employee class inherits from the Person class, allowing it to use the display method defined in the Person class.

Types of Inheritance

Python supports several types of inheritance:

  1. Single Inheritance: A child class inherits from a single parent class.
  2. Multiple Inheritance: A child class inherits from multiple parent classes.
  3. Multilevel Inheritance: A child class inherits from a parent class, which in turn inherits from another parent class.
  4. Hierarchical Inheritance: Multiple child classes inherit from the same parent class.
  5. Hybrid Inheritance: A combination of two or more types of inheritance.

Method Overriding and super()

Method overriding allows a child class to provide a specific implementation for a method that is already defined in its parent class. The super() function is used to call a method from the parent class.

Python
class Animal:
   def speak(self):
       return "Some sound"
class Dog(Animal):
   def speak(self):
       return "Woof!"
# Creating an instance of the Dog class
dog = Dog()
print(dog.speak()) # Output: Woof!

In this example, the Dog class overrides the speak method of the Animal class.

Using super() Function

The super() function allows you to call methods from the parent class. This is useful for initializing the parent class’s attributes in the child class.

Python
class Person:
   def __init__(self, name, age):
       self.name = name
       self.age = age
class Student(Person):
   def __init__(self, name, age, grade):
       super().__init__(name, age)
       self.grade = grade
# Creating an instance of the Student class
student = Student("Alice", 20, "A")
print(student.name, student.age, student.grade) # Output: Alice 20 A

In this example, super().__init__(name, age) calls the __init__ method of the Person class to initialize the name and age attributes.

Conclusion

Inheritance in Python is a powerful feature that promotes code reusability and allows for the creation of a hierarchical relationship between classes. By understanding and utilizing inheritance, you can create more efficient and maintainable code.

Categories
Computer Science

Object Oriented Programming – Abstraction

What is Abstraction?

Abstraction is a fundamental concept in Object-Oriented Programming (OOP) that focuses on hiding the internal implementation details of a class or method while exposing only the necessary functionality. This simplifies code interaction, reduces complexity, and enhances maintainability.

In Python, abstraction is achieved using abstract classes and abstract methods, which are defined in the abc module.

Abstract Classes and Methods

An abstract class serves as a blueprint for other classes. It cannot be instantiated directly and must be subclassed. Abstract classes contain one or more abstract methods, which are declared but not implemented. Subclasses must provide their own implementation for these methods.

For example:

Python
from abc import ABC, abstractmethod
# Abstract class
class Animal(ABC):
   @abstractmethod
   def make_sound(self):
       pass # Abstract method with no implementation
# Concrete subclass
class Dog(Animal):
   def make_sound(self):
       return "Bark"
# Instantiate the subclass
dog = Dog()
print(dog.make_sound()) # Output: Bark

In this example, Animal is an abstract class with an abstract method make_sound(). The Dog class implements the method, allowing it to be instantiated.

Key Components of Abstraction

  1. Abstract Methods: Declared using the @abstractmethod decorator, these methods must be implemented by subclasses.
  2. Concrete Methods: Fully implemented methods in an abstract class that can be inherited by subclasses.
  3. Abstract Properties: Declared using @property and @abstractmethod, these enforce property implementation in subclasses.

Example of Abstract Properties

Python
from abc import ABC, abstractmethod
class Vehicle(ABC):
   @property
   @abstractmethod
   def wheels(self):
       pass
class Car(Vehicle):
   @property
   def wheels(self):
       return 4
car = Car()
print(car.wheels) # Output: 4

Here, wheels is an abstract property in the Vehicle class, and the Car class provides its implementation.

Benefits of Abstraction

  • Simplifies Code: Users interact with high-level functionality without worrying about internal details.
  • Encapsulation: Sensitive or unnecessary details are hidden, reducing misuse or accidental changes.
  • Flexibility: Subclasses can define specific behaviors while adhering to a consistent structure.
  • Maintainability: Internal changes in abstract classes do not affect external code.

Important Considerations

  • Abstract classes cannot be instantiated directly. Attempting to do so raises a TypeError.
  • Subclasses must implement all abstract methods and properties; otherwise, they too become abstract and cannot be instantiated.

Example of Instantiation Error

Python
from abc import ABC, abstractmethod
class Shape(ABC):
   @abstractmethod
   def area(self):
       pass
# Attempting to instantiate an abstract class
shape = Shape() # Raises TypeError

Abstraction in Python is a powerful tool for designing robust and scalable applications by enforcing a clear structure and hiding unnecessary complexity.

Categories
Computer Science

Solving Problem: Sliding Window Maximum

Closeup binary coding screen by Markus Spiske is licensed under CC-CC0 1.0

Arrays and Strings

Problem Statement:

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

Python:

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # Write your code here
        max_array = []
        for i in range(0, len(nums) - k + 1):
            window_max = max(nums[i:i+k])
            max_array.append(window_max)
        return max_array