Search code examples
pythonwhile-loopfactorial

Using primitive operators to find factorial of N up to K depth


Having difficulty coming up with a solution using:

  1. iteration/control-flow and
  2. accumulation.

More than just a solution, would prefer having an answer with hints and explanation.

def falling(n, k):
    """Compute the falling factorial of N to depth K.

    >>> falling(6, 3)  # 6 * 5 * 4
    120
    >>> falling(4, 3)  # 4 * 3 * 2
    24
    >>> falling(4, 1)  # 4
    4
    >>> falling(4, 0)
    1
    """
    fact = n
    i = 0    
    while i <= k:
        fact = fact * fact - 1
        i += 1
        n -= 1
    return fact

Solution

  • def falling(n, k):
        """Compute the falling factorial of N to depth K.
    
        >>> falling(6, 3)  # 6 * 5 * 4
        120
        >>> falling(4, 3)  # 4 * 3 * 2
        24
        >>> falling(4, 1)  # 4
        4
        >>> falling(4, 0)
        1
        """
        
        if k == 0:
            return 1
    
        return_value = 1
    
        counter = 0
    
        while counter < k:
            return_value = return_value * (n-counter)
            counter += 1
    
        return return_value
    

    Ignoring k=0 you have want to multiply k numbers starting with n and ending with n-k. The above loops k times and since i will increment by 1 starting from 0, you can simply subtract it from n to get the next number to multiply by.

    Edit: Making sure k=0 is returning 1 always by returning early

    Edit2: Removing built in range function

    Edit3: making sure to go k deep