Coding Level 1

by

Modulo % 

Dividend=Divisor*Quotient + Remainder
Python

  • a % b returns the remainder when a is divided by b.
  • The result of a % b will always be in the range [0, b-1]
  • If a is less than b, a % b will be equal to a.

Example to show the modulus operator:

  • 10 % 3 = 1, (10 = 3*3+1 )
  • 15 % 4 = 3, because (15=4*3+3)
  • 8 % 2 = 0, because (8=2*4+0)
  • 2%10 = 2, becuase (2 = 10*0 + 2)

Refer

Extract Last Digit(s) of a Number

n = 12323
print(n%10) #3
Python

Digit separation

my_number = 12345

while my_number>0:
    reminder = my_number%10
    my_number = int(my_number/10)
    print(reminder)
    
#Output 
5
4
3
2
1
Python

Reverse a number

def reverse_number(n: int) -> int:
    """
    Reverse the digits of a given integer.

    Args:
        n (int): The number to reverse.
    Returns:
        int: The reversed number.
    """
    reversed_num = 0
    while n > 0:
        digit = n % 10               # Extract the last digit
        n //= 10                     # Remove the last digit
        reversed_num = reversed_num * 10 + digit  # Append digit to reversed number
    return reversed_num


# Example usage
a = 123456789
print(reverse_number(a)) #987654321
Python

Decimal to binary

def decimal_to_binary(n):
    binary = ""
    if n == 0:
        return "0"
    while n > 0:
        remainder = n % 2
        binary = str(remainder)+binary
        n = n // 2  # Integer division by 2
    return binary

# Example usage
num = 6
print(decimal_to_binary(num))  # Output: "110"
Python

Using Bitwise



def decimal_to_binary(n):
    binary = ""
    while(n>0):
        binary=str(n&1) + binary
        n = n>>1
    return binary
print(d_to_b(145)) #10010001
Python

  • Right >>, equivalent to divide by 2
  • n&1 gives the last bit

Refer

Binary to Decimal



def binary_to_decimal(binary_str):

    number = 0
    count  =len(binary_str)
    power  = 0

    for b in binary_str:
        number = number+int(b)*2**(count-power-1)
        power+=1

    return number

print(binary_to_decimal("1100")) #12
Python

Using bitwise

def binary_to_decimal(binary_str):
    decimal = 0
    for digit in binary_str:
        decimal = (decimal << 1) | int(digit)  # Shift left and add bit
    return decimal

# Example usage
binary_str = "1101"
print(binary_to_decimal(binary_str))  # Output: 13
Python

Array

Reverse an Array


arr = [1, 2, 3, 4, 5,6,7,8,9,10]
start = 0
lst   = len(arr)-1

while start<=lst:
    arr[lst],arr[start] = arr[start],arr[lst]
    start+=1
    lst-=1

print(arr)
Python

Array Rotation

Method 1: Using Mod (%)

Consider it as a circular array and use the property of mod, which requires an extra array.


lst    = [1,2,3,4,5,6,7,8,9,10]
length = len(lst)

k = 8

#right rotaion
result = [0]*length
for i in range(length):
    j = (i+k)%length
    result[j] = lst[i]
print(result)            #[3, 4, 5, 6, 7, 8, 9, 10, 1, 2]


# Left rotation 1st variation 
result = [0]*length
for i in range(length):
    j = (i - k) % length
    result[j] = lst[i]
print(result) # [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]
Python

Note:

Point 1

  • In the case of left rotation, we may have a negative value for i – k
  • Negative mod works differently in a few programming languages. Refer.
  • In Python, it works fine.

Point 2:

  • j may be negative, like lst[-3] ( = lst[7] )
  • Python can handle it, but few programming languages may not support this

Left Rotation 2nd variation 



#Right rotaion :2nd variation

result = [0]*length
for i in range(length):
    j = (i-k)%length
    result[i] = lst[j]
print(result)  #[3, 4, 5, 6, 7, 8, 9, 10, 1, 2]


#Left rotaion :2nd variation
result = [0]*length
for i in range(length):
    j = (i+k)%length
    result[i] = lst[j]
print(result)            # [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]
Python

  • Same as right rotation, but j used in lst
  • Same to use in all programming languages

Method 2: Two Pointers

  • The method requires extra space
  • Two pointer is used for reversing the array
  • In-place rotation

Concept

d = 8 # shift by right or left

if d > n
  d = d % n  #  rotating by d or rotating by d % n are effectively the same.
  
  
Example: 
d = 8  # We want to rotate by 8 positions
n = 5  # Array length is 5: [1,2,3,4,5]

Instead of rotating 8 times
We can rotate just 8 % 5 = 3 times
Same result, less work!
  
 
 
Rotating 8 times
# Rotating [1,2,3,4,5] left by:
# 1 position → [2,3,4,5,1] 
# 2 positions → [3,4,5,1,2]
# 3 positions → [4,5,1,2,3]
# 4 positions → [5,1,2,3,4]
# 5 positions → [1,2,3,4,5] ← Back to original!
# 6 positions → [2,3,4,5,1] ← Same as 1 position!
# 7 positions → [3,4,5,1,2] ← Same as 2 positions!
# 8 positions → [4,5,1,2,3] ← Same as 3 positions! 
  
  
  
Instead of rotating 8 times
#We can rotate just 8 % 5 = 3 times
#Same result, less work!
Python

When rotating an array, you might get a rotation value d that’s larger than the array length. This creates unnecessary work!. Just rotate d % n

# Left rotate in-place using reverse
def reverse(arr, start, end):
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start+= 1
        end-= 1

def left_rotate_in_place(arr, d): 
    n = len(arr)
    d = d % n                    # Optimization for large d
    reverse(arr, 0, d-1)         # Step 1: Reverse first d elements
    reverse(arr, d, n-1)         # Step 2: Reverse remaining elements  
    reverse(arr, 0, n-1)         # Step 3: Reverse entire array

def right_rotate(arr, d):   
    n = len(arr)
    d %= n                           # Optimization
    reverse(arr, 0, n - d - 1)       # Step 1: Reverse first (n-d) elements
    reverse(arr, n - d, n - 1)       # Step 2: Reverse last d elements
    reverse(arr, 0, n - 1)           # Step 3: Reverse entire array
    
    
'''

Left rotate

Original: [1, 2, 3, 4, 5, 6, 7]
Left rotate by d = 3

Step 1: Reverse first 3 elements [1,2,3]
Result: [3, 2, 1, 4, 5, 6, 7]

Step 2: Reverse remaining elements [4,5,6,7]  
Result: [3, 2, 1, 7, 6, 5, 4]

Step 3: Reverse entire array
Result: [4, 5, 6, 7, 1, 2, 3]



Rigt Rotate

Original: [1, 2, 3, 4, 5, 6, 7]
Right rotate by d = 3

Step 1: Reverse first (7-3=4) elements [1,2,3,4]
Result: [4, 3, 2, 1, 5, 6, 7]

Step 2: Reverse last 3 elements [5,6,7]
Result: [4, 3, 2, 1, 7, 6, 5]

Step 3: Reverse entire array
Result: [5, 6, 7, 1, 2, 3, 4] 

'''
Python

Logic Behind the Reverse Method

Suppose: Original array = A B

Left Rotation

  • where A = first d elements (to rotate)
  • B = remaining n-d elements
[A B] => [B A]
Python

Procedure

  • Step 1: Reverse A → A’ (A reversed)
  • Step 2: Reverse B → B’ (B reversed)
  • Step 3: Reverse the whole → (A’ + B’)’

Right Rotation

  • Same logic as left
  • where A = first n-d elements
  • B = last d elements to rotate

Refer to Leet 189: Array Rotation

Method 3: Use if slicing


d = d % n

lst = lst[d:] + lst[:d] #Left rotation
Python


d = d % n

lst  = lst[length-d:] + lst[:length-d]

or 

lst =  lst[-d:] + lst[:-d] # Tricky
Python

LCM and GCD

Refer

Linked List

Refer

Nth Largest Number

nums = [3, 2, 1, 5, 6, 4]
N = 2

# Expected Output: 5 (the 2nd largest)
Python

Method 1: Using Sorting

def nth_largest(nums, n):
    return sorted(nums, reverse=True)[n - 1]
Python

  • Time Complexity: O(n log n)
  • Good for small lists or quick scripts.

Method 2: Using Min-Heap of Size N (Optimised for large arrays)

import heapq

def nth_largest(nums, n):
    min_heap = nums[:n]
    heapq.heapify(min_heap)
    
    for num in nums[n:]:
        if num > min_heap[0]:
            heapq.heappushpop(min_heap, num)
    
    return min_heap[0]
Python

  • Time Complexity: O(n log n) worst-case, but better if n is small compared to the list.
  • Best when the list is very large and n is small.

Read More

Roman Numerals

Roman → Integer (Reading)

Concept

  • Roman symbols are written in descending value order
  • If a smaller value appears before a bigger value, it is a subtractive case
  • Otherwise, values are added normally

Rule

  • If current < next → subtract
  • Else → add

Historical / Rule-Based Reason (Core Why)

Roman numerals were designed with two strict goals:

  • Keep numbers short
  • Avoid repeating the same symbol more than 3 times

To achieve this, the Romans introduced subtractive notation.

Example 1

For 4
IIII ❌ (4 times I)
IV  → 5 - 1 = 4

For 9
VIIII ❌
IX → 10 - 1 = 9
Python

Example 2

MCMXCIV

M = 1000 

C = 100
M = 1000, suddenly a digit came bigger than previous one. So subtract it: 1000-100
X = 10
C = 100, again problem: 100-10 
I : 1
V : 5 , again problem: 5-1


= 1000 + (1000-100) + (100-10) + (5-1) = 1994
Python

Code

class Solution:
    def romanToInt(self, s: str) -> int:
        roman = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }

        total = 0
        for i in range(len(s)):
            if i + 1 < len(s) and roman[s[i]] < roman[s[i + 1]]:
                total -= roman[s[i]]
            else:
                total += roman[s[i]]

        return total
Python

Integer → Roman

Concept

  • Roman numerals must follow fixed construction rules
  • Some numbers use subtractive symbols (4 = IV, 9 = IX, etc.)
  • We must explicitly define all valid Roman building blocks
  • Use a greedy approach (largest to smallest)
1000 → M
900  → CM
500  → D
400  → CD
100  → C
90   → XC
50   → L
40   → XL
10   → X
9    → IX
5    → V
4    → IV
1    → I
Python

Why are special symbols required?

  • Without them:
    • 4 becomes IIII ❌
    • 90 becomes LXXXX ❌
  • Roman numerals forbid more than 3 repetitions
  • Hence, subtractive symbols must be predefined
  • Note: these additional symbols are not required for roman to integer

Code

class Solution:
    def intToRoman(self, num: int) -> str:
        values = [
            (1000, "M"),
            (900, "CM"),
            (500, "D"),
            (400, "CD"),
            (100, "C"),
            (90, "XC"),
            (50, "L"),
            (40, "XL"),
            (10, "X"),
            (9, "IX"),
            (5, "V"),
            (4, "IV"),
            (1, "I")
        ]

        result = ""

        for value, symbol in values:
            while num >= value:
                result += symbol
                num -= value

        return result
Python

Final Summary

  • Roman → Integer: Read symbols → compare → add or subtract
  • Integer → Roman: Build symbols → greedy → predefined valid blocks

Example 

num = 1994

1994 ≥ 1000 → M
1994 - 1000 = 994

994 ≥ 900 → CM
994 - 900 = 94

94 ≥ 90 → XC
94 - 90 = 4

4 ≥ 4 → IV
4 - 4 = 0


Roman: MCMXCIV
Python

Leet Problems

Leave a Comment