Jobs

Interviews

Discussions

Max Difference You Can Get From Changing an Integer

Medium

Asked by:

63 views

Topics:

Greedy AlgorithmsStrings

You are given an integer num. You will apply the following steps to num two separate times:

Pick a digit x (0 <= x <= 9).
Pick another digit y (0 <= y <= 9). Note y can be equal to x.
Replace all the occurrences of x in the decimal representation of num by y.

Let a and b be the two results from applying the operation to num independently.

Return the max difference between a and b.

Note that neither a nor b may have any leading zeros, and must not be 0.

Example 1:

Input: num = 555
Output: 888
Explanation: The first time pick x = 5 and y = 9 and store the new integer in a.
The second time pick x = 5 and y = 1 and store the new integer in b.
We have now a = 999 and b = 111 and max difference = 888

Example 2:

Input: num = 9
Output: 8
Explanation: The first time pick x = 9 and y = 9 and store the new integer in a.
The second time pick x = 9 and y = 1 and store the new integer in b.
We have now a = 9 and b = 1 and max difference = 8

Constraints:

1 <= num <= 10⁸

Try coding it in LeetCode

Max Difference You Can Get From Changing an Integer

Medium

Asked by:

63 views

Topics:

Greedy AlgorithmsStrings

You are given an integer num. You will apply the following steps to num two separate times:

Pick a digit x (0 <= x <= 9).
Pick another digit y (0 <= y <= 9). Note y can be equal to x.
Replace all the occurrences of x in the decimal representation of num by y.

Let a and b be the two results from applying the operation to num independently.

Return the max difference between a and b.

Note that neither a nor b may have any leading zeros, and must not be 0.

Example 1:

Input: num = 555
Output: 888
Explanation: The first time pick x = 5 and y = 9 and store the new integer in a.
The second time pick x = 5 and y = 1 and store the new integer in b.
We have now a = 999 and b = 111 and max difference = 888

Example 2:

Input: num = 9
Output: 8
Explanation: The first time pick x = 9 and y = 9 and store the new integer in a.
The second time pick x = 9 and y = 1 and store the new integer in b.
We have now a = 9 and b = 1 and max difference = 8

Constraints:

1 <= num <= 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 is the range of values for the integer input? Can it be negative or zero?
What should I return if the input is a single-digit number?
Are there any leading zeros in the original integer that I need to consider when replacing digits?
If multiple maximum differences are possible, should I return any one of them or a specific one?
Is the input always guaranteed to be a valid integer, or should I handle cases where the input is invalid (e.g., null or not a number)?

Brute Force Solution

Approach

The brute force method solves this problem by trying every single possible change we can make to the number. We explore all combinations of replacements and pick the pair that gives us the biggest difference.

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

Consider the input number as a sequence of digits.
Start by trying to replace each digit in the original number with every other possible digit (0 through 9).
For each replacement you make, create two new numbers: one where the digit is replaced with '9' and one where it's replaced with '0' (or '1' if the first digit is replaced with '0' to keep it a valid number).
Calculate the difference between the original number and each of the newly created numbers.
Repeat the digit replacement process for every digit position in the original number.
Keep track of the largest difference you find during all these replacements.
After you've explored every possible replacement, the largest difference you've tracked is your answer.

Code Implementation

def max_difference_brute_force(number):
    number_string = str(number)
    max_difference = 0

    for index in range(len(number_string)):

        # Try replacing the current digit with 9
        new_number_string_max = list(number_string)
        digit_to_replace = number_string[index]
        for i in range(len(new_number_string_max)):
            if new_number_string_max[i] == digit_to_replace:
                new_number_string_max[i] = '9'
        new_number_max = int("".join(new_number_string_max))
        max_difference = max(max_difference, abs(number - new_number_max))

        # Handle leading zero case for min replacement
        if index == 0:
            replacement_digit = '1'
        else:
            replacement_digit = '0'

        # Try replacing the current digit with 0 or 1
        new_number_string_min = list(number_string)
        for i in range(len(new_number_string_min)):
            if new_number_string_min[i] == digit_to_replace:
                new_number_string_min[i] = replacement_digit
        new_number_min = int("".join(new_number_string_min))

        max_difference = max(max_difference, abs(number - new_number_min))

    return max_difference

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each digit of the input number, which has n digits. For each digit, it performs a constant amount of operations: creating two new numbers by replacing the digit with '9' and '0' (or '1' for the first digit), and calculating the difference. Since the number of operations is proportional to the number of digits in the input number, the time complexity is O(n).

Space Complexity

O(1) – The described brute force approach primarily involves iterative replacements and comparisons. While temporary numbers are created during the replacement process, the algorithm only needs to store a constant number of variables such as the original number, the modified number, and the current maximum difference found. The space needed to store these variables doesn't depend on the number of digits in the input integer. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to find the biggest and smallest possible numbers you can create by replacing a single digit in the original number. We do this by strategically finding the digits to change to maximize and minimize the result without exploring every possible combination.

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

To get the biggest number, start by looking at the leftmost digit. If it's not a 9, replace all occurrences of that digit with a 9. This is the biggest change possible.
If the leftmost digit is already a 9, move to the next digit until you find one that's not a 9. Replace all occurrences of that digit with a 9.
To get the smallest number, again start with the leftmost digit. If it's not a 1, replace all occurrences of that digit with a 1. This minimizes the number as much as possible.
If the leftmost digit is a 1, move to the next digit. If that digit is not a 0 and not a 1, replace all occurrences of that digit with a 0. This makes the number even smaller.
If the second digit is already a 0 or 1, keep moving to the next digits until you find one that isn't 0 or 1. Replace all occurrences of that digit with a 0.
Subtract the smallest number from the biggest number to get the maximum difference.

Code Implementation

def max_diff(number):
    number_string = str(number)

    def find_max(number_string):
        for digit_index, digit in enumerate(number_string):
            if digit != '9':
                # Replace first non-9 digit with 9.
                digit_to_replace = digit
                break
        else:
            return int(number_string)
        maximized_string = number_string.replace(digit_to_replace, '9')
        return int(maximized_string)

    def find_min(number_string):
        if number_string[0] != '1':
            # Replace leading digit with 1.
            digit_to_replace = number_string[0]
            minimized_string = number_string.replace(digit_to_replace, '1')
            return int(minimized_string)
        else:
            # Find next digit to replace with 0.
            for digit_index, digit in enumerate(number_string[1:]):
                if digit != '0' and digit != '1':
                    # Replace the first non-0 and non-1 with 0.
                    digit_to_replace = digit
                    break
            else:
                return int(number_string)
            minimized_string = number_string.replace(digit_to_replace, '0')
            return int(minimized_string)

    maximized_number = find_max(number_string)
    minimized_number = find_min(number_string)

    # The difference gives us the maximum possible difference.
    return maximized_number - minimized_number

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the input number (n digits) a maximum of four times: once to find the digit to replace for the largest number, once to replace the digit with 9, once to find the digit to replace for the smallest number, and once to replace the digit with 0 or 1. Each iteration performs a linear scan of the digits. Therefore, the time complexity is O(4n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm converts the input integer to a string to facilitate digit replacement. This string representation requires O(N) space, where N is the number of digits in the input integer. Although the operations largely involve in-place replacements within this string, the initial string conversion itself consumes auxiliary space proportional to the number of digits. Therefore, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or negative input integer	Return 0 or throw IllegalArgumentException as the problem implies a positive integer input.
Single digit input (e.g., 5)	Replacing the single digit with another digit will necessarily result in a smaller number, so return 9 - input (replacing the digit with 9) minus input.
Input integer with leading zeros (e.g., 0123)	Convert the integer to a string and remove any leading zeros as the int itself will not contain leading zeros.
Integer where all digits are the same (e.g., 1111)	Replace all digits with 9 and then with 0 or 1 for min value according to rules.
Large integer that might cause integer overflow during calculations	Use long data type to store intermediate values and the result to prevent overflow.
An integer that already contains 0 or 9	The algorithm should correctly handle digits of 0 or 9 present in the initial number.
Maximum integer value (Integer.MAX_VALUE)	Check if the replacement of any digit with 9 will cause an overflow when parsing the result to an integer, and use long if it does.
Number with only two distinct digits.	The algorithm will still successfully replace digits according to the defined rules to maximize and minimize values.

Null or negative input integer

How to Handle:

Return 0 or throw IllegalArgumentException as the problem implies a positive integer input.

Single digit input (e.g., 5)

How to Handle:

Replacing the single digit with another digit will necessarily result in a smaller number, so return 9 - input (replacing the digit with 9) minus input.

Input integer with leading zeros (e.g., 0123)

How to Handle:

Convert the integer to a string and remove any leading zeros as the int itself will not contain leading zeros.

Integer where all digits are the same (e.g., 1111)

How to Handle:

Replace all digits with 9 and then with 0 or 1 for min value according to rules.

Large integer that might cause integer overflow during calculations

How to Handle:

Use long data type to store intermediate values and the result to prevent overflow.

An integer that already contains 0 or 9

How to Handle:

The algorithm should correctly handle digits of 0 or 9 present in the initial number.

Maximum integer value (Integer.MAX_VALUE)

How to Handle:

Check if the replacement of any digit with 9 will cause an overflow when parsing the result to an integer, and use long if it does.

Number with only two distinct digits.

How to Handle:

The algorithm will still successfully replace digits according to the defined rules to maximize and minimize values.

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 is the range of values for the integer input? Can it be negative or zero?
What should I return if the input is a single-digit number?
Are there any leading zeros in the original integer that I need to consider when replacing digits?
If multiple maximum differences are possible, should I return any one of them or a specific one?
Is the input always guaranteed to be a valid integer, or should I handle cases where the input is invalid (e.g., null or not a number)?

Brute Force Solution

Approach

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

Consider the input number as a sequence of digits.
Start by trying to replace each digit in the original number with every other possible digit (0 through 9).
For each replacement you make, create two new numbers: one where the digit is replaced with '9' and one where it's replaced with '0' (or '1' if the first digit is replaced with '0' to keep it a valid number).
Calculate the difference between the original number and each of the newly created numbers.
Repeat the digit replacement process for every digit position in the original number.
Keep track of the largest difference you find during all these replacements.
After you've explored every possible replacement, the largest difference you've tracked is your answer.

Code Implementation

def max_difference_brute_force(number):
    number_string = str(number)
    max_difference = 0

    for index in range(len(number_string)):

        # Try replacing the current digit with 9
        new_number_string_max = list(number_string)
        digit_to_replace = number_string[index]
        for i in range(len(new_number_string_max)):
            if new_number_string_max[i] == digit_to_replace:
                new_number_string_max[i] = '9'
        new_number_max = int("".join(new_number_string_max))
        max_difference = max(max_difference, abs(number - new_number_max))

        # Handle leading zero case for min replacement
        if index == 0:
            replacement_digit = '1'
        else:
            replacement_digit = '0'

        # Try replacing the current digit with 0 or 1
        new_number_string_min = list(number_string)
        for i in range(len(new_number_string_min)):
            if new_number_string_min[i] == digit_to_replace:
                new_number_string_min[i] = replacement_digit
        new_number_min = int("".join(new_number_string_min))

        max_difference = max(max_difference, abs(number - new_number_min))

    return max_difference

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

To get the biggest number, start by looking at the leftmost digit. If it's not a 9, replace all occurrences of that digit with a 9. This is the biggest change possible.
If the leftmost digit is already a 9, move to the next digit until you find one that's not a 9. Replace all occurrences of that digit with a 9.
To get the smallest number, again start with the leftmost digit. If it's not a 1, replace all occurrences of that digit with a 1. This minimizes the number as much as possible.
If the leftmost digit is a 1, move to the next digit. If that digit is not a 0 and not a 1, replace all occurrences of that digit with a 0. This makes the number even smaller.
If the second digit is already a 0 or 1, keep moving to the next digits until you find one that isn't 0 or 1. Replace all occurrences of that digit with a 0.
Subtract the smallest number from the biggest number to get the maximum difference.

Code Implementation

def max_diff(number):
    number_string = str(number)

    def find_max(number_string):
        for digit_index, digit in enumerate(number_string):
            if digit != '9':
                # Replace first non-9 digit with 9.
                digit_to_replace = digit
                break
        else:
            return int(number_string)
        maximized_string = number_string.replace(digit_to_replace, '9')
        return int(maximized_string)

    def find_min(number_string):
        if number_string[0] != '1':
            # Replace leading digit with 1.
            digit_to_replace = number_string[0]
            minimized_string = number_string.replace(digit_to_replace, '1')
            return int(minimized_string)
        else:
            # Find next digit to replace with 0.
            for digit_index, digit in enumerate(number_string[1:]):
                if digit != '0' and digit != '1':
                    # Replace the first non-0 and non-1 with 0.
                    digit_to_replace = digit
                    break
            else:
                return int(number_string)
            minimized_string = number_string.replace(digit_to_replace, '0')
            return int(minimized_string)

    maximized_number = find_max(number_string)
    minimized_number = find_min(number_string)

    # The difference gives us the maximum possible difference.
    return maximized_number - minimized_number

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or negative input integer	Return 0 or throw IllegalArgumentException as the problem implies a positive integer input.
Single digit input (e.g., 5)	Replacing the single digit with another digit will necessarily result in a smaller number, so return 9 - input (replacing the digit with 9) minus input.
Input integer with leading zeros (e.g., 0123)	Convert the integer to a string and remove any leading zeros as the int itself will not contain leading zeros.
Integer where all digits are the same (e.g., 1111)	Replace all digits with 9 and then with 0 or 1 for min value according to rules.
Large integer that might cause integer overflow during calculations	Use long data type to store intermediate values and the result to prevent overflow.
An integer that already contains 0 or 9	The algorithm should correctly handle digits of 0 or 9 present in the initial number.
Maximum integer value (Integer.MAX_VALUE)	Check if the replacement of any digit with 9 will cause an overflow when parsing the result to an integer, and use long if it does.
Number with only two distinct digits.	The algorithm will still successfully replace digits according to the defined rules to maximize and minimize values.

Null or negative input integer

How to Handle:

Return 0 or throw IllegalArgumentException as the problem implies a positive integer input.

Single digit input (e.g., 5)

How to Handle:

Replacing the single digit with another digit will necessarily result in a smaller number, so return 9 - input (replacing the digit with 9) minus input.

Input integer with leading zeros (e.g., 0123)

How to Handle:

Convert the integer to a string and remove any leading zeros as the int itself will not contain leading zeros.

Integer where all digits are the same (e.g., 1111)

How to Handle:

Replace all digits with 9 and then with 0 or 1 for min value according to rules.

Large integer that might cause integer overflow during calculations

How to Handle:

Use long data type to store intermediate values and the result to prevent overflow.

An integer that already contains 0 or 9

How to Handle:

The algorithm should correctly handle digits of 0 or 9 present in the initial number.

Maximum integer value (Integer.MAX_VALUE)

How to Handle:

Check if the replacement of any digit with 9 will cause an overflow when parsing the result to an integer, and use long if it does.

Number with only two distinct digits.

How to Handle:

The algorithm will still successfully replace digits according to the defined rules to maximize and minimize values.