Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Combination Sum

    Given the target value N and an array of allowed positive numbers, you are asked to count the ways to write N as the sum of those numbers.
    So, if the allowed values are for instance [1, 2, 3], and the number N is 4, we can sum those numbers up in 7 different ways:
    All the 7 ways to sum up 1, 2, 3 to obtain 4
    1. 1 + 1 + 1 + 1
    1. 1 + 1 + 2
    1. 1 + 2 + 1
    1. 2 + 1 + 1
    1. 1 + 3
    1. 3 + 1
    1. 2 + 2
    This is a classic dynamic programming problem, which can be solved by keeping a state d[sum] which represents all the possible ways to obtain the sum by combining the allowed numbers:
    N = ...
    nums = [...]
    d = [0] * (N + 1)          # d[i] = all the combinations that sum up to `i`
    d[0] = 1                   # There is 1 way to get a 0 - not to take any numbers
    
    for i in range(1, N + 1):  # Try to obtain all the numbers sequentially 1...N
        for num in nums:       # Try to get `d[i]` with the help of `num`
            if i - num >= 0:   # If it's possible to obtain `i` from `num`
                d[i] += d[i - num]
    print(d[N])
    So, our state d[i] is the number of ways we can obtain i using the allowed numbers nums. We initialize everything with 0 except d[0] which we set to 1 as we can obtain 0 in only 1 way - by not using any of the allowed numbers. For all the other numbers, we look at all the possible ways we can obtain the numbers using nums.
    If we can obtain the number 11 (d[11]) with let’s say 5 different ways and we know that we were able to obtain the number 8 (d[8]) with 3 different ways, then in case there is 3 in the nums array, we can obtain the number 11 with all the ways we’ve found so far + all the ways we could obtain 8 (d[8]) and then put the number 3 next to it.
    Let’s simulate the algorithm on the sample input:
    nums = [1, 2, 3] and N = 4
    1. d = [1, 0, 0, 0, 0] β†’ 1 way to obtain 0 and the rest are 0s
    1. i = 1 num = 1 β‡’ d[1] += d[0] β‡’ d = [1, 1, 0, 0, 0] num = 2 β‡’ i - num < 0 num = 3 β‡’ i - num < 0
    1. i = 2 num = 1 β‡’ d[2] += d[1] β‡’ d = [1, 1, 1, 0, 0] num = 2 β‡’ d[2] += d[0] β‡’ d = [1, 1, 2, 0, 0] num = 3 β‡’ i - num < 0
    1. i = 3 num = 1 β‡’ d[3] += d[2] β‡’ d = [1, 1, 2, 2, 0] num = 2 β‡’ d[3] += d[1] β‡’ d = [1, 1, 2, 3, 0] num = 3 β‡’ d[3] += d[0] β‡’ d = [1, 1, 2, 4, 0]
    1. i = 4 num = 1 β‡’ d[4] += d[3] β‡’ d = [1, 1, 2, 4, 4] num = 2 β‡’ d[4] += d[2] β‡’ d = [1, 1, 2, 4, 6] num = 3 β‡’ d[4] += d[1] β‡’ d = [1, 1, 2, 4, 7]
    1. print(d[4]) β†’ prints 7
    Β 

    Challenge - Dice Combinations

    If you throw a die, it produces a number from 1 to 6. You are asked to compute the number of ways to obtain the number n by summing up together dice rolls.
    notion image

    Input

    The input contains a single integer n (1 ≀ n ≀ ).

    Output

    The program should print the number of ways you can throw a die to obtain the number n as a sum of those throws. As the answer can get very large, you are asked to print it modulo .

    Examples

    Input
    Output
    2
    2
    3
    4

    Explanation

    1. 2 β†’ 1 + 1, 2
    1. 3 β†’ 1 + 1 + 1, 1 + 2, 2 + 1, 3
    Β 

    Constraints

    Time limit: 2.5 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue