Fundamentals of Problem Solving

Number Operations

Extracting the Last Digit of a Number

• Operation: num % 10

• Explanation: The modulo operation returns the last digit of a number.

• Example:

    val num = 123
    val lastDigit = num % 10 // lastDigit will be 3
  

• Potential Use:

  • Palindrome Check: To check if a number is a palindrome, you often need to extract the last digit repeatedly and compare it with the first digit of the number.

  • Reversing a Number: When reversing a number, extracting the last digit is the first step to construct the reversed number.

Removing the Last Digit of a Number

• Operation: num / 10

• Explanation: Integer division by 10 removes the last digit of the number.

• Example:

    val num = 123
    val withoutLastDigit = num / 10 // withoutLastDigit will be 12
  

• Potential Use:

  • Reversing a Number: To reverse a number, you will repeatedly remove the last digit using this operation and build the reversed number.

  • Digit Counting: This operation helps in counting how many digits a number has by repeatedly dividing the number by 10 until it becomes 0.

Adding a New Digit to a Number

• Operation: num = num * 10 + temp

• Explanation: Multiplies the number by 10 and adds a new digit at the end.

• Example:

    var num = 12
    val temp = 3
    num = num * 10 + temp // num will be 123
  

• Potential Use:

  • Reversing a Number: When reversing a number, you use this operation to add the last digit (which you extracted) to the reversed number.

  • Constructing Numbers: In some problems, where you need to reconstruct a number or append digits, this is a commonly used approach.

Multiplying a Number by Powers of 10

• Operation: num * 10^k (or num * Math.pow(10.0, k).toInt() for specific powers)

• Explanation: Multiplies a number by 10 raised to the power k, effectively shifting its digits to the left.

• Example:

    val num = 5
    val k = 2
    val result = num * Math.pow(10.0, k.toDouble()).toInt() // result will be 500
  

• Potential Use:

  • Shifting Digits: In problems where you need to shift a number’s digits (such as for constructing or extracting specific digits), multiplying by powers of 10 is useful.

  • Padding Numbers: Sometimes, you need to add zeroes to a number or adjust its magnitude by multiplying by powers of 10.

Extracting Specific Digits from a Number

• Operation: (num / (10^k)) % 10

• Explanation: To get the k-th digit from the right (0-based index).

• Example:

    val num = 12345
    val k = 2
    val specificDigit = (num / Math.pow(10.0, k.toDouble()).toInt()) % 10 // specificDigit will be 3
  

• Potential Use:

  • Digit Extraction: This operation is essential when you need to extract a specific digit from a number for tasks like Palindrome Checking, Digit-Based Operations, or Digit Manipulation.

Counting Digits of a Number

• Operation: Repeatedly divide the number by 10 until it becomes 0.

• Explanation: Count how many times you can divide by 10 before reaching 0.

• Example:

    var num = 12345
    var count = 0
    while (num != 0) {
        num /= 10
        count++
    }
    // count will be 5
  

• Potential Use:

  • Palindrome Check: Counting digits is often the first step when checking if a number is a palindrome (to know how many iterations you need for comparison).

  • Reversing a Number: Knowing the number of digits can help in correctly constructing a reversed number, especially in place-based solutions.

Checking Even or Odd

• Operation: num % 2 == 0 (Even), num % 2 != 0 (Odd)

• Explanation: The modulo operation checks if a number is divisible by 2.

• Example:

    val num = 4
    val isEven = num % 2 == 0 // isEven will be true
  

• Potential Use:

  • Parity-Based Problems: This operation is fundamental in problems that distinguish between even and odd numbers, such as Even/Odd Patterns, Divisibility Tests, and Subset Sum Problems.

Sum of Digits

• Operation: num % 10 to extract the last digit and num / 10 to remove it.

• Explanation: Sum all the digits of the number by extracting them.

• Example:

    var num = 123
    var sum = 0
    while (num != 0) {
        sum += num % 10
        num /= 10
    }
    // sum will be 6
  

• Potential Use:

  • Digit-Sum Problems: Used in tasks where the sum of digits is needed, such as Digital Root, Divisibility Tests (e.g., checking divisibility by 9), or Palindrome Checks.

Adding Multiples of a Number

• Operation: Sum the multiples of a given number within a specified range.

• Explanation: To add multiples of a number, identify the sequence of multiples within a given range and sum them.

• Example:

    fun sumMultiples(n: Int, limit: Int): Int {
        var sum = 0
        for (i in 1..limit) {
            if (i % n == 0) {
                sum += i
            }
        }
        return sum
    }
  
    val result = sumMultiples(3, 15) // result will be 45
  

• Potential Use:

  • Arithmetic Series: Adding multiples is useful in solving problems related to arithmetic series, where you need to find the sum of a sequence of numbers.

  • Optimization Problems: In programming challenges, adding multiples can help optimize solutions, such as finding the sum of numbers that meet specific criteria (e.g., multiples of 3 or 5).

Reversing Digits of a Number

• Operation: Repeatedly extract the last digit and construct the reversed number.

• Explanation: Reverse a number using a loop and basic arithmetic.

• Example:

    var num = 123
    var reversed = 0
    while (num != 0) {
        val digit = num % 10
        reversed = reversed * 10 + digit
        num /= 10
    }
    // reversed will be 321
  

• Potential Use:

  • Palindrome Check: Reversing a number is a key part of checking if a number is a palindrome.

  • Digit Manipulation: Reversing digits is a common task in problems that require digit reorganization or processing.

Power of a Number

• Operation: Math.pow(base, exp) or use loops for iterative multiplications.

• Explanation: Computes the power of a number, i.e., base^exp.

• Example:

    val base = 2
    val exp = 3
    val power = Math.pow(base.toDouble(), exp.toDouble()).toInt() // power will be 8
  

• Potential Use:

  • Exponentiation: This operation is crucial for problems that require exponential growth, geometric progressions, or problems like modular exponentiation.

Checking Divisibility

• Operation: num % divisor == 0

• Explanation: Use the modulo operation to check divisibility.

• Example:

    val num = 10
    val divisor = 5
    val isDivisible = num % divisor == 0 // isDivisible will be true
  

• Potential Use:

  • Divisibility Problems: Essential for problems that require checking whether a number is divisible by another number, such as LCM and GCD calculations, Divisibility Tests, and Prime Checking.

Swapping Two Numbers

• Operation: Using a temporary variable or a tuple

• Explanation: Swap the values of two variables.

• Example:

    var a = 5
    var b = 10
    val temp = a
    a = b
    b = temp
    // a will be 10, b will be 5
  

• Potential Use:

  • Sorting Algorithms: Swapping is a fundamental operation used in bubble sort, selection sort, and quicksort.

  • In-Place Reversal: Swapping is often used when reversing arrays, lists, or strings in-place (e.g., in reverse algorithms).

  • Two-Pointer Problems: Swapping can be crucial in problems where you manipulate elements from both ends of a collection (e.g., partitioning arrays).

Finding the Maximum/Minimum of Two Numbers

• Operation: max(a, b), min(a, b)

• Explanation: Returns the maximum or minimum of two numbers.

• Example:

    val a = 5
    val b = 10
    val maximum = maxOf(a, b) // maximum will be 10
  

• Potential Use:

  • Conditional Logic: Often used to decide between two values or handle different cases in algorithms (e.g., knapsack problem or interval problems).

  • Sliding Window Problems: In problems where you need to keep track of the maximum or minimum within a sliding window.

String Operations

String Length

• Operation: str.length

• Explanation: Get the length (number of characters) of a string.

• Example:

    val str = "hello"
    val length = str.length // length will be 5
  

• Potential Use:

  • String Processing: The length of a string is important in many string manipulation tasks, like substring extraction, palindrome checks, or index-based string manipulations.

Converting a String to Integer

• Operation: str.toInt()

• Explanation: Converts a string representation of a number to an integer.

• Example:

    val str = "12345"
    val num = str.toInt() // num will be 12345
  

• Potential Use:

  • Input Parsing: Often used to convert string input (from the user or file) into an integer for numerical operations.

  • Palindrome Check: Used when you need to convert string representations of numbers into integers to check if a number is a palindrome.

String to Char Array

• Operation: str.toCharArray()

• Explanation: Converts a string into a character array.

• Example:

    val str = "hello"
    val charArray = str.toCharArray() // charArray will be ['h', 'e', 'l', 'l', 'o']
  

• Potential Use:

  • String Manipulation: Useful when you need to work with individual characters, like in anagram checking, reversing strings, or character-based algorithms.

  • Palindrome Check: Can be used for two-pointer techniques in palindrome checking, where you compare characters from both ends of the string.

Character to Integer (ASCII Value)

• Operation: char.toInt()

• Explanation: Converts a character to its corresponding ASCII/Unicode value.

• Example:

    val char = 'A'
    val asciiValue = char.toInt() // asciiValue will be 65
  

• Potential Use:

  • Character Comparison: This is useful in problems that involve sorting characters or comparing character-based operations. For example, checking if two strings are anagrams or determining the lexicographical order.

  • Encryptions/Decoding: Many encryption algorithms (like Caesar Cipher) rely on shifting ASCII values of characters.

Integer to Character

• Operation: num.toChar()

• Explanation: Converts an integer to its corresponding character based on its ASCII/Unicode value.

• Example:

    val num = 65
    val char = num.toChar() // char will be 'A'
  

• Potential Use:

  • Character Generation: When working with custom encoding, shifting characters, or generating characters dynamically, you may need to convert numbers back into characters.

String Substring

• Operation: str.substring(startIndex, endIndex)

• Explanation: Extracts a portion of a string from startIndex to endIndex.

• Example:

    val str = "hello"
    val substring = str.substring(1, 4) // substring will be "ell"
  

• Potential Use:

  • String Parsing: Extract specific parts of a string, such as when you are parsing date formats, extracting domain names, or working with regular expressions.

  • Sliding Window Algorithms: Many problems like longest substring without repeating characters use substring operations.

Reversing a String

• Operation: str.reversed()

• Explanation: Returns the reverse of the string.

• Example:

    val str = "hello"
    val reversed = str.reversed() // reversed will be "olleh"
  

• Potential Use:

  • Palindrome Check: A string is a palindrome if it reads the same forwards and backwards. Reversing the string is a common approach to check for this.

  • Reversing Words: Commonly used in problems where you need to reverse the order of words in a sentence while keeping the words themselves intact.

String Concatenation

• Operation: str1 + str2 or str1.concat(str2)

• Explanation: Concatenate two strings together.

• Example:

    val str1 = "hello"
    val str2 = "world"
    val concatenated = str1 + str2 // concatenated will be "helloworld"
  

• Potential Use:

  • Building Strings Dynamically: In many problems, such as forming a sentence or constructing patterns, you need to concatenate strings.

  • Efficient String Construction: Concatenation is used in problems that involve string formatting or manipulating parts of strings, like word search or URL construction.

Checking if a String is Empty

• Operation: str.isEmpty()

• Explanation: Checks if a string is empty (i.e., has length 0).

• Example:

    val str = ""
    val isEmpty = str.isEmpty() // isEmpty will be true
  

• Potential Use:

  • Input Validation: Often used to check if a string input is empty, particularly in input parsing problems, or when dealing with user-provided strings.

  • Edge Case Handling: In recursive or iterative algorithms, ensuring a string is not empty before processing can be crucial for correctness.

Finding a Character in a String

• Operation: str.indexOf(char)

• Explanation: Returns the index of the first occurrence of the specified character.

• Example:

    val str = "hello"
    val index = str.indexOf('e') // index will be 1
  

• Potential Use:

  • Character Searching: Used to locate characters in a string. For example, checking if a specific character is present in a string.

  • Substring Search: In many string-based search algorithms like Rabin-Karp or Knuth-Morris-Pratt, this operation helps find the position of a character or substring.

Reversing a String with a StringBuilder

• Operation: StringBuilder().append(str).reverse()

• Explanation: Uses StringBuilder to efficiently reverse a string.

• Example:

    val str = "hello"
    val reversed = StringBuilder().append(str).reverse().toString() // reversed will be "olleh"
  

• Potential Use:

  • Palindrome Checking: A common method for reversing a string for palindrome problems.

  • String Manipulation: Efficiently handle string modifications like reversals and in-place transformations.

Splitting a String into Words

• Operation: str.split(" ")

• Explanation: Splits a string into an array of substrings using the specified delimiter (e.g., space).

• Example:

    val str = "hello world"
    val words = str.split(" ") // words will be ["hello", "world"]
  

• Potential Use:

  • Word Parsing: Used in problems like word counting, sentence parsing, and splitting input strings into meaningful units.

  • Tokenization: A common operation in text analysis tasks or Natural Language Processing (NLP), where splitting text into individual words is essential.

Removing Leading and Trailing Spaces from a String

• Operation: str.trim()

• Explanation: Removes any leading and trailing spaces from the string.

• Example:

    val str = "  hello  "
    val trimmed = str.trim() // trimmed will be "hello"
  

• Potential Use:

  • Input Validation: Often used when dealing with user inputs to clean the string before processing, like trimming spaces from a username or password.

  • Parsing Strings: Useful in tokenization or string comparison when you want to eliminate unwanted spaces before performing operations.

Converting a String to Uppercase or Lowercase

• Operation: str.toUpperCase() or str.toLowerCase()

• Explanation: Converts all characters in a string to either uppercase or lowercase.

• Example:

    val str = "hello"
    val upper = str.toUpperCase() // upper will be "HELLO"
  

• Potential Use:

  • Case-Insensitive Comparisons: Often used in problems where the case of characters should not matter, such as checking if two strings are the same (case-insensitive) or when comparing inputs from different sources.

  • Standardization: When data from different sources need to be normalized for further processing or analysis.

Array Operations

Summing Elements in an Array

• Operation: array.sum()

• Explanation: Computes the sum of all elements in an array.

• Example:

    val array = arrayOf(1, 2, 3, 4)
    val sum = array.sum() // sum will be 10
  

• Potential Use:

  • Sum-Based Problems: Used in problems where you need to compute the sum of elements in an array, such as subarray sum, prefix sum, or average calculations.

  • Dynamic Programming: Often used in knapsack problems or when calculating subset sums.

Finding the Index of an Element in an Array

• Operation: array.indexOf(element)

• Explanation: Returns the index of the first occurrence of an element in an array (returns -1 if the element is not found).

• Example:

    val array = arrayOf(1, 2, 3, 4)
    val index = array.indexOf(3) // index will be 2
  

• Potential Use:

  • Searching Algorithms: Useful in problems that require linear search or index-based operations.

  • Partitioning Arrays: Used in algorithms like quicksort or binary search for locating specific elements or determining boundaries.

Checking for Even/Odd in an Array

• Operation: Using num % 2 == 0 to check if even

• Explanation: Checks if elements in an array are even or odd.

• Example:

    val array = arrayOf(1, 2, 3, 4)
    val evens = array.filter { it % 2 == 0 } // evens will be [2, 4]
  

• Potential Use:

  • Classification: Problems that involve categorizing elements as even or odd (e.g., separate even and odd numbers).

  • Number Property Problems: Problems that focus on properties like divisibility or parity (e.g., odd-even sorting or number classification).

Converting an Array to a Set

• Operation: array.toSet()

• Explanation: Converts an array into a set, removing duplicate elements.

• Example:

    val array = arrayOf(1, 2, 2, 3)
    val set = array.toSet() // set will be {1, 2, 3}
  

• Potential Use:

  • Unique Element Extraction: Useful in problems where you need to ensure all elements are unique, such as finding distinct elements or removing duplicates.

  • Set Operations: Enables the use of set operations like union, intersection, and difference for problem-solving.

Mathematical Operations

Converting a Number to Binary

• Operation: Integer.toBinaryString(num)

• Explanation: Converts an integer to its binary representation as a string.

• Example:

    val num = 5
    val binary = Integer.toBinaryString(num) // binary will be "101"
  

• Potential Use:

  • Bit Manipulation: In algorithms that require bitwise operations (like binary search or bitmasking), converting numbers to binary helps understand the binary form of the number.

  • Binary Representation: Used when problems require handling binary numbers, bitwise operations, or computing powers of two.

Converting a Binary String to Decimal

• Operation: Integer.parseInt(binaryString, 2)

• Explanation: Converts a binary string to its decimal integer representation.

• Example:

    val binaryString = "101"
    val decimal = Integer.parseInt(binaryString, 2) // decimal will be 5
  

• Potential Use:

  • Binary to Decimal Conversion: This is used when converting binary inputs (e.g., from binary files, bitmasks, or other sources) to a more usable integer format.

  • Bitwise Algorithms: In algorithms that deal with binary manipulations, such as counting set bits or applying bitwise AND, OR, or XOR operations.