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 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 circular array and use the property of mod and requires 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 negative value for i – k
  • Negative mod works differently in few programming language. Refer.
  • In Python it works fine.

Point 2:

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

Left Rotation 2nd variation 

#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 language

Method 2: Two Pointers

  • Method requires extra space
  • Two pointer is used for reversing the array
  • Inplace 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 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 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 (Optimized 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 list is very large and n is small.

Read More

Leet Problems

Leave a Comment