Rearrange Digits Without Adjacent Sums Above Nine

Question

The candidate is asked to rearrange a list of digits such that no two adjacent digits sum to a value greater than nine.

Codemia · Accepted Answer

To solve the problem of rearranging digits without adjacent sums exceeding nine, I will use a greedy algorithm. The idea is to sort the digits and then try to place them in a manner that minimizes the chances of adjacent digits summing above nine. We'll start by placing the smallest digits first and check the sum condition as we build the final arrangement.

1. **Sort the digits** in ascending order.
2. **Initialize an empty result list** to store the rearranged digits.
3. **Iterate through the sorted list**, adding digits to the result list while checking the sum of the last digit added and the current digit.
4. If adding the current digit violates the sum condition, try to find the next valid digit.
5. **Return the result list** as the final rearranged digits.

The time complexity of this algorithm is O(n log n) due to the sorting step, where n is the number of digits. The subsequent iteration through the digits is O(n), making the overall complexity dominated by the sorting step. The space complexity is O(n) for storing the result.

```python
def rearrange_digits(digits):
    digits.sort()
    result = []
    for digit in digits:
        if not result or (result[-1] + digit <= 9):
            result.append(digit)
        else:
            # Find a valid position for the current digit
            for i in range(len(result)):  
                if (result[i] + digit <= 9):
                    result.insert(i, digit)
                    break
    return result
```
This code sorts the digits and then builds the result list while ensuring the sum condition is met.

It's important to consider edge cases such as:
- An empty list of digits, which should return an empty list.
- A list where all digits are the same or where all digits are 0, which should also return the same list.
- Large numbers of digits that could lead to performance issues, which we can address with our efficient sorting and checking mechanism.

Rearrange Digits Without Adjacent Sums Above Nine

Amazon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Amazon Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string