Jobs

Interviews

Discussions

Minimum Division Operations to Make Array Non Decreasing

Medium

Asked by:

32 views

Topics:

ArraysGreedy Algorithms

You are given an integer array nums.

Any positive divisor of a natural number x that is strictly less than x is called a proper divisor of x. For example, 2 is a proper divisor of 4, while 6 is not a proper divisor of 6.

You are allowed to perform an operation any number of times on nums, where in each operation you select any one element from nums and divide it by its greatest proper divisor.

Return the minimum number of operations required to make the array non-decreasing.

If it is not possible to make the array non-decreasing using any number of operations, return -1.

Example 1:

Input: nums = [25,7]

Output: 1

Explanation:

Using a single operation, 25 gets divided by 5 and nums becomes [5, 7].

Example 2:

Input: nums = [7,7,6]

Output: -1

Example 3:

Input: nums = [1,1,1,1]

Output: 0

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Try coding it in LeetCode

Minimum Division Operations to Make Array Non Decreasing

Medium

Asked by:

32 views

Topics:

ArraysGreedy Algorithms

You are given an integer array nums.

You are allowed to perform an operation any number of times on nums, where in each operation you select any one element from nums and divide it by its greatest proper divisor.

Return the minimum number of operations required to make the array non-decreasing.

If it is not possible to make the array non-decreasing using any number of operations, return -1.

Example 1:

Input: nums = [25,7]

Output: 1

Explanation:

Using a single operation, 25 gets divided by 5 and nums becomes [5, 7].

Example 2:

Input: nums = [7,7,6]

Output: -1

Example 3:

Input: nums = [1,1,1,1]

Output: 0

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values in the input array?
Can the input array be empty or null?
If the array is already non-decreasing, should I return 0?
What should I return if it's impossible to make the array non-decreasing using division operations?
Can you define 'division operation' more precisely? Specifically, what happens with the fractional part of the result? Is it truncated, rounded up, or rounded down?

Brute Force Solution

Approach

The brute force method for this problem involves checking every possible combination of division operations. We explore all ways to divide numbers in the input, evaluating if a non-decreasing sequence is achieved. This is achieved by exhaustively trying every possible choice at each stage.

Here's how the algorithm would work step-by-step:

Consider no divisions at all in the beginning.
Then, try dividing just the first number by all possible divisors.
Next, try dividing just the second number by all possible divisors.
Continue this process, trying divisions for each individual number in the original input.
After trying all single divisions, consider all possible pairs of divisions. This means trying every possible divisor for two different numbers in the input.
Keep repeating the above, increasing the number of divided numbers until you've tried all possible combinations of divisions across the entire input sequence.
For each combination of divisions, check if the resulting numbers form a non-decreasing sequence.
If the sequence is non-decreasing, note the number of division operations performed.
Finally, after checking all possible division combinations, find the minimum number of division operations that resulted in a non-decreasing sequence.

Code Implementation

def minimum_division_operations_to_make_array_non_decreasing(numbers):
    array_length = len(numbers)
    minimum_operations = float('inf')

    # Iterate through all possible combinations of divisions
    for i in range(1 << (array_length * 10)):
        temp_numbers = numbers[:]
        division_count = 0
        divisor_index = 0

        # Determine the divisors to apply based on the bitmask
        for number_index in range(array_length):
            for _ in range(10):
                if (i >> divisor_index) & 1:
                    # Divide by 2 if the corresponding bit is set
                    temp_numbers[number_index] /= 2
                    division_count += 1
                divisor_index += 1

        # Check if the resulting array is non-decreasing
        is_non_decreasing = True
        for index in range(array_length - 1):
            if temp_numbers[index] > temp_numbers[index + 1]:
                is_non_decreasing = False
                break

        # Update minimum operations if needed
        if is_non_decreasing:
            minimum_operations = min(minimum_operations, division_count)

    # Consider the case with no divisions
    is_non_decreasing = True
    for index in range(array_length - 1):
        if numbers[index] > numbers[index + 1]:
            is_non_decreasing = False
            break

    if is_non_decreasing:
        minimum_operations = min(minimum_operations, 0)

    if minimum_operations == float('inf'):
        return -1
    else:
        return minimum_operations

Big(O) Analysis

Time Complexity

O(n * d^n) – The described brute force approach explores all possible combinations of divisions. For each of the n numbers in the input array, we can potentially divide it by some divisor. Let 'd' represent the number of possible divisors for a single number (in the worst case, this could depend on the magnitude of the number itself). The algorithm iterates through all possible subsets of elements in the array, and for each subset, it tries all combinations of divisors for those elements. The number of such combinations grows exponentially with n, specifically as d^n (each number has d choices). Then, for each combination of divisions, the algorithm checks if the resulting array is non-decreasing, which takes O(n) time. Combining these factors, the total time complexity becomes O(n * d^n), where the n comes from verifying the non-decreasing order.

Space Complexity

O(N*2^N) – The brute force approach explores all possible combinations of divisions. This generates a call tree where, at each level representing an element in the input array, we either divide it by a divisor or don't. This leads to up to 2^N branches where N is the number of elements in the input array. For each of these branches (combinations of divisions), we store a temporary array of size N representing the modified input. Thus, the auxiliary space complexity is driven by the N length array that is recreated for each potential combination, leading to a space complexity of O(N * 2^N).

Optimal Solution

Approach

The core idea is to move from the end of the list to the beginning, figuring out the least number of changes needed to make each number less than or equal to the one after it. We use a method called Dynamic Programming, which stores intermediate results to avoid repeating calculations and make the entire process much faster.

Here's how the algorithm would work step-by-step:

Begin at the end of the list since the last number doesn't need any adjustments.
Move backwards through the list, one number at a time.
For each number, determine if it's already less than or equal to the next number. If so, we don't need to do anything.
If the current number is bigger, we need to figure out the fewest divisions needed to make it smaller than or equal to the next number.
We'll explore dividing the current number by different values to find the smallest division that achieves this, keeping track of the divisions we've tried and the number of steps taken.
The clever trick is to reuse the information we've already computed for the numbers after the current one. By storing the best strategies for making those numbers non-decreasing, we can quickly apply those solutions to the current number.
Continue this process until you reach the beginning of the list. The final result is the total number of divisions you performed along the way, representing the fewest changes to make the entire list non-decreasing.

Code Implementation

def min_division_operations(numbers):
    list_length = len(numbers)
    division_counts = [0] * list_length

    for i in range(list_length - 2, -1, -1):
        # Iterate backwards, skipping the last element.
        if numbers[i] <= numbers[i + 1]:
            continue

        min_divisions_needed = float('inf')

        # Determine divisions needed to become non-decreasing.
        for divisor in range(1, numbers[i] + 1):
            divided_value = numbers[i] / divisor

            if divided_value <= numbers[i + 1]:
                divisions_needed = 1

                if divisions_needed < min_divisions_needed:
                    min_divisions_needed = divisions_needed

        numbers[i] = numbers[i] // (numbers[i] // numbers[i+1] if numbers[i] > numbers[i+1] else 1)
        division_counts[i] = 1

        # Update the minimum number of divisions.
        division_counts[i] += division_counts[i+1]

    total_divisions = 0
    for count in division_counts:
        total_divisions += count

    return sum(division_counts)

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates backward through the array of size n. For each element, it explores different division factors to make it less than or equal to the next element. The number of divisions can grow logarithmically with respect to the initial value of the current element in the array, because we're essentially performing a search for the optimal divisor. Thus, the time complexity is dominated by n multiplied by the logarithmic search for the divisor at each element, resulting in O(n log n).

Space Complexity

O(N) – The dynamic programming approach, as described, stores intermediate results to avoid redundant calculations. This implies the use of a data structure, likely an array or a list, to store the minimum number of divisions needed for subproblems ending at each index. Therefore, auxiliary space is used to store results for each of the N elements in the input array. This results in space usage that grows linearly with the input size, giving a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as an empty array is already non-decreasing.
Array with only one element	Return 0, as a single-element array is inherently non-decreasing.
Array already non-decreasing	Return 0, as no divisions are needed.
Array with all elements being the same value	If the array is non-decreasing return 0 otherwise return the number of needed operations.
Array with strictly decreasing elements	Handle this case appropriately by performing required divisions to ensure the array becomes non-decreasing, keeping the division count to a minimum.
Large input array with elements close to INT_MAX	Ensure that intermediate calculations involving multiplication or division do not cause integer overflows, using appropriate data types (e.g., long long).
Array with elements that require many divisions to become non-decreasing	The algorithm should handle cases that need repeated division of certain elements gracefully, ensuring it eventually leads to non-decreasing array.
Input array contains zero	Handle the division by zero error carefully by either skipping that element or making it a very small number to proceed.

Null or empty input array

How to Handle:

Return 0, as an empty array is already non-decreasing.

Array with only one element

How to Handle:

Return 0, as a single-element array is inherently non-decreasing.

Array already non-decreasing

How to Handle:

Return 0, as no divisions are needed.

Array with all elements being the same value

How to Handle:

If the array is non-decreasing return 0 otherwise return the number of needed operations.

Array with strictly decreasing elements

How to Handle:

Handle this case appropriately by performing required divisions to ensure the array becomes non-decreasing, keeping the division count to a minimum.

Large input array with elements close to INT_MAX

How to Handle:

Ensure that intermediate calculations involving multiplication or division do not cause integer overflows, using appropriate data types (e.g., long long).

Array with elements that require many divisions to become non-decreasing

How to Handle:

The algorithm should handle cases that need repeated division of certain elements gracefully, ensuring it eventually leads to non-decreasing array.

Input array contains zero

How to Handle:

Handle the division by zero error carefully by either skipping that element or making it a very small number to proceed.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values in the input array?
Can the input array be empty or null?
If the array is already non-decreasing, should I return 0?
What should I return if it's impossible to make the array non-decreasing using division operations?
Can you define 'division operation' more precisely? Specifically, what happens with the fractional part of the result? Is it truncated, rounded up, or rounded down?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider no divisions at all in the beginning.
Then, try dividing just the first number by all possible divisors.
Next, try dividing just the second number by all possible divisors.
Continue this process, trying divisions for each individual number in the original input.
After trying all single divisions, consider all possible pairs of divisions. This means trying every possible divisor for two different numbers in the input.
Keep repeating the above, increasing the number of divided numbers until you've tried all possible combinations of divisions across the entire input sequence.
For each combination of divisions, check if the resulting numbers form a non-decreasing sequence.
If the sequence is non-decreasing, note the number of division operations performed.
Finally, after checking all possible division combinations, find the minimum number of division operations that resulted in a non-decreasing sequence.

Code Implementation

def minimum_division_operations_to_make_array_non_decreasing(numbers):
    array_length = len(numbers)
    minimum_operations = float('inf')

    # Iterate through all possible combinations of divisions
    for i in range(1 << (array_length * 10)):
        temp_numbers = numbers[:]
        division_count = 0
        divisor_index = 0

        # Determine the divisors to apply based on the bitmask
        for number_index in range(array_length):
            for _ in range(10):
                if (i >> divisor_index) & 1:
                    # Divide by 2 if the corresponding bit is set
                    temp_numbers[number_index] /= 2
                    division_count += 1
                divisor_index += 1

        # Check if the resulting array is non-decreasing
        is_non_decreasing = True
        for index in range(array_length - 1):
            if temp_numbers[index] > temp_numbers[index + 1]:
                is_non_decreasing = False
                break

        # Update minimum operations if needed
        if is_non_decreasing:
            minimum_operations = min(minimum_operations, division_count)

    # Consider the case with no divisions
    is_non_decreasing = True
    for index in range(array_length - 1):
        if numbers[index] > numbers[index + 1]:
            is_non_decreasing = False
            break

    if is_non_decreasing:
        minimum_operations = min(minimum_operations, 0)

    if minimum_operations == float('inf'):
        return -1
    else:
        return minimum_operations

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Begin at the end of the list since the last number doesn't need any adjustments.
Move backwards through the list, one number at a time.
For each number, determine if it's already less than or equal to the next number. If so, we don't need to do anything.
If the current number is bigger, we need to figure out the fewest divisions needed to make it smaller than or equal to the next number.
We'll explore dividing the current number by different values to find the smallest division that achieves this, keeping track of the divisions we've tried and the number of steps taken.
The clever trick is to reuse the information we've already computed for the numbers after the current one. By storing the best strategies for making those numbers non-decreasing, we can quickly apply those solutions to the current number.
Continue this process until you reach the beginning of the list. The final result is the total number of divisions you performed along the way, representing the fewest changes to make the entire list non-decreasing.

Code Implementation

def min_division_operations(numbers):
    list_length = len(numbers)
    division_counts = [0] * list_length

    for i in range(list_length - 2, -1, -1):
        # Iterate backwards, skipping the last element.
        if numbers[i] <= numbers[i + 1]:
            continue

        min_divisions_needed = float('inf')

        # Determine divisions needed to become non-decreasing.
        for divisor in range(1, numbers[i] + 1):
            divided_value = numbers[i] / divisor

            if divided_value <= numbers[i + 1]:
                divisions_needed = 1

                if divisions_needed < min_divisions_needed:
                    min_divisions_needed = divisions_needed

        numbers[i] = numbers[i] // (numbers[i] // numbers[i+1] if numbers[i] > numbers[i+1] else 1)
        division_counts[i] = 1

        # Update the minimum number of divisions.
        division_counts[i] += division_counts[i+1]

    total_divisions = 0
    for count in division_counts:
        total_divisions += count

    return sum(division_counts)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as an empty array is already non-decreasing.
Array with only one element	Return 0, as a single-element array is inherently non-decreasing.
Array already non-decreasing	Return 0, as no divisions are needed.
Array with all elements being the same value	If the array is non-decreasing return 0 otherwise return the number of needed operations.
Array with strictly decreasing elements	Handle this case appropriately by performing required divisions to ensure the array becomes non-decreasing, keeping the division count to a minimum.
Large input array with elements close to INT_MAX	Ensure that intermediate calculations involving multiplication or division do not cause integer overflows, using appropriate data types (e.g., long long).
Array with elements that require many divisions to become non-decreasing	The algorithm should handle cases that need repeated division of certain elements gracefully, ensuring it eventually leads to non-decreasing array.
Input array contains zero	Handle the division by zero error carefully by either skipping that element or making it a very small number to proceed.

Null or empty input array

How to Handle:

Return 0, as an empty array is already non-decreasing.

Array with only one element

How to Handle:

Return 0, as a single-element array is inherently non-decreasing.

Array already non-decreasing

How to Handle:

Return 0, as no divisions are needed.

Array with all elements being the same value

How to Handle:

If the array is non-decreasing return 0 otherwise return the number of needed operations.

Array with strictly decreasing elements

How to Handle:

Handle this case appropriately by performing required divisions to ensure the array becomes non-decreasing, keeping the division count to a minimum.

Large input array with elements close to INT_MAX

How to Handle:

Ensure that intermediate calculations involving multiplication or division do not cause integer overflows, using appropriate data types (e.g., long long).

Array with elements that require many divisions to become non-decreasing

How to Handle:

The algorithm should handle cases that need repeated division of certain elements gracefully, ensuring it eventually leads to non-decreasing array.

Input array contains zero

How to Handle:

Handle the division by zero error carefully by either skipping that element or making it a very small number to proceed.