Category: Coding

Categories
Coding Computer Science Python

Solving Problem: Validating Roman Numbers

Coding on a computer screen by Markus Spiske is licensed under CC-CC0 1.0

Using Regex Pattern to validate if a Roman number is valid

Problem Statement: Validate if a roman number is between 1 and 3999

Solution:

Python
regex_pattern = r'^M{0,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$'	# Do not delete 'r'.
import re
print(str(bool(re.match(regex_pattern, input()))))

This is the classic Roman numeral validation regex (for 1–3999)

Roman Numerals

Roman numerals originated in ancient Rome and remained widely used through the Middle Ages. They rely on fixed-value symbols rather than positional notation.

Core Symbols

  • I = 1
  • V = 5
  • X = 10
  • L = 50
  • C = 100
  • D = 500
  • M = 1000

Additive Rule

Place symbols from largest to smallest left to right:

  • VIII = 5 + 1 + 1 + 1 = 8
  • LXX = 50 + 10 + 10 = 70

Subtractive Rule

Place a smaller symbol before a larger one to subtract:

  • IV = 4
  • IX = 9
  • XL = 40
  • CM = 900
Common Conversions
NumberRomanNumberRoman
1I20XX
4IV40XL
9IX90XC
100C400CD
500D900CM
1000M——

Regex for validating Roman Numerals from 1-3999:

regex = r’^M{0,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$’

Breakdown:

^

Start of string.

M{0,3} 

""     = 0
M      = 1000
MM     = 2000
MMM    = 3000

(CM|CD|D?C{0,3})

Hundreds place:

CM     = 900
CD     = 400
D?C{0,3}

D?C{0,3} covers:

""     = 0
C      = 100
CC     = 200
CCC    = 300
D      = 500
DC     = 600
DCC    = 700
DCCC   = 800

(XC|XL|L?X{0,3})

XC     = 90
XL     = 40
L?X{0,3}

L?X{0,3} covers:

""     = 0
X      = 10
XX     = 20
XXX    = 30
L      = 50
LX     = 60
LXX    = 70
LXXX   = 80

(IX|IV|V?I{0,3})

Ones place:

IX     = 9
IV     = 4
V?I{0,3}

covers:

""     = 0
I      = 1
II     = 2
III    = 3
V      = 5
VI     = 6
VII    = 7
VIII   = 8

$

End of string.

Valid Matches

I
IV
IX
X
XL
XC
CD
CM
MCMXC
MCMXCIV
MMMCMXCIX   (3999)

Invalid Matches:

IIII
VV
IC
XM
MMMM
VX
IL
MCMC

References

Validating Roman Numerals | HackerRank

Python Regular Expressions  |  Python Education  |  Google for Developers

Categories
Coding Computer Science Python

Solving Problem: Maximize It!

Computer coding on a screen by Markus Spiske is licensed under CC-CC0 1.0

Problem Statement:

Refer: Maximize It! | HackerRank

Solution:

maximize.py
Python
import itertools
def f(x):
    return x**2      
def maximized(K,M):
    S = []
    li1 = []
    for i in range(K):
        inp1 = list(map(int,input().split()))
        li = inp1[1:]
        li1.append(li)
        
    combinations = list(itertools.product(*li1))
    
    for i in combinations:
        Si = sum([f(x) for x in list(i)])%M
        S.append(Si)
    
    return max(S)
    
        
if __name__== "__main__":
    inp = list(map(int,input().split()))
    K, M = inp[0], inp[1]
    
    print(maximized(K, M))

Output:

All tests passed!

Please feel free to drop any suggestions or input.

Happy 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: Incorrect Regex

Coding on a computer screen by Markus Spiske is licensed under CC-CC0 1.0

(Python)

Problem Statement:

You are given a string S.
Your task is to check whether S is a valid regex.

Input Format

The first line contains an integer T, the number of test cases.
The next T line contains the string S.

Constraints

0 < T < 100

Output Format

Print “True” or “False” for each test case without quotes.

Sample Input

2
.*\+
.*+

Sample Output

True
False

Explanation

.*\+ : Valid regex.
.*+: Has the error multiple repeat. Hence, it is invalid.

Solution:

validate_regex.py
Python
import re
# validate regex
def is_valid_regex(T, patterns):
    for i in range(0, T):
        S = str(raw_input())
        try:
            re.compile(S)
            print(True)
        except:
            print(False)
            
if __name__ == "__main__":
    # User input
    T = int(input())
    patterns = [r".*\+"]
    output = is_valid_regex(T, patterns)

Output:

Reference:

Incorrect Regex | 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