Tag: Coding

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

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

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