Given the number in the record which can be present up to 10 ^ 5 digits. In this number, you can change any two numbers in places. Among all these replacements, you need to find the one at which the largest number is obtained.

Over O (n²) is easily solved. How to solve for O (n) or for O (n⋅log (n)) ?

Examples:

1234 => 4231 9997754321 => 9997754321
  • The second example is not at all indicative. And what is meant by заменить ? Swap? - αλεχολυτ

2 answers 2

Write the digits of the original number in the array a . (If there is a lot of digits for a number, then most likely the number is already given to you exactly in this form.) Copy the array into array b and sort it in descending order.

Find the first index such that a[i] != b[i] . If there is no such index, the permutation is not needed, the order is optimal. Let it be the index k . Obviously, b[k] >= a[i] for i >= k , and b[k] != a[k] by the choice of k . Therefore, b[k] is the maximum of the remaining numbers.

Obviously, b[k] , b[k+1] , ... is a permutation of the numbers a[k] , a[k+1] , ..., therefore b[k] == a[l] for some l > k . ( l != k , since b[k] != a[k] ). Take the largest such l .

The permutation of the indices k and l is the desired one.

Complexity: O ( n log n ) {sort} + O ( n ) {search k } + O ( n ) {search l } = O ( n log n ).

Update: As we sort the numbers, the complexity of the sorting can be reduced to O ( n ) by applying sorting by counting . The total complexity is O ( n ).

Note : You can get rid of the additional array b , if you replace it simply with the number of 9-ok, 8-ok, 7-ok, etc. (this information is used in sorting by count), due to some complication of the code. Thus, we get only O (1) additional memory.

  • And just 2 passes ( O (n) ) sorting with maximum search is not enough? - avp
  • @avp: Clarified the answer. - VladD
  • For sure. Small add. array (by the way, I thought and realized that simple sorting with a maximum does not solve, since the 2 largest digits can already be at the beginning of the number) - avp
  • Thanks for the detailed reply - pank
  • @SergeyPestov: Please! - VladD

Here is the implementation on Python of a linear ( O(n) ) algorithm with constant additional memory ( O(1) ), described in the answer @VladD :

 #!/usr/bin/env python3 from collections import Counter def make_largest_by_swapping_2_digits(digits): """O(n) time, O(m) space""" # find where given number differs from the largest number with the same digits multiplicity = Counter(digits) # count how many times each digit occurs all_digits = sorted(multiplicity, reverse=True) # m digits in decreasing order largest = (d for d in all_digits for _ in range(multiplicity[d])) for k, (a, b) in enumerate(zip(digits, largest)): if a != b: break else: # already largest possible return # nothing to swap # find on the right where a == b j = next(len(digits) - i for i, a in enumerate(reversed(digits), 1) if a == b) digits[k], digits[j] = digits[j], digits[k] # swap

Example:

 digits = [1,2,3,4] print('before', *digits) make_largest_by_swapping_2_digits(digits) print('after ', *digits)

Result

 before 1 2 3 4 after 4 2 3 1

Notes on the code:

  • Counter() simply counts how many times each digit occurs:

     print(Counter(str(9997754321))) # -> Counter({'9': 3, '7': 2, '5': 1, '4': 1, '3': 1, '2': 1, '1': 1})

    Memory consumption is O(m) , where m is not more than 10 for the decimal system. Can be considered constant.

    Counter is essentially a multiset here (a set of numbers with repetitions). If you restrict the type of numbers to only decimal, then you can use a simple array instead of Counter:

     multiplicity = [0] * 10 for d in digits: multiplicity[d] += 1

  • largest is the largest number made up of the same numbers as the input number. A generator is used for presentation, so additional memory is needed for only one digit at each moment. O(1)

  • enumerate(zip()) allows you to bypass two sequences at the same time one pair of elements at a time, tracking the current index:

     >>> list(enumerate(zip(range(3), "abc"))) [(0, (0, 'a')), (1, (1, 'b')), (2, (2, 'c'))]

  • make_largest_by_swapping_2_digits(digits) accepts any variable sequence ( list , bytearray , mmap , etc) with hashable elements that can be compared.

For example, for large numbers recorded in a file, you can directly work with mmap (assuming that a single digit in the byte fits):

 import mmap with open('много-цифр.txt', 'r+b', 0) as file, \ mmap.mmap(file.fileno(), 0, access=mmap.ACCESS_WRITE) as digits: make_largest_by_swapping_2_digits(digits)

After executing the code, the много-цифр.txt will contain the new number — a change in place occurs.

  • Cool, Python even has a special class for counting sort in essence. - VladD
  • one
    @VladD Counter essentially multiset here (a set of numbers with repetitions). If you restrict the type of numbers to only decimal, then you can use a simple array instead of Counter: multiplicity = [0]*10; for d in digits: multiplicity[d]+=1 multiplicity = [0]*10; for d in digits: multiplicity[d]+=1 (that's all Counter does in the first example). - jfs
  • Result 1234 -> 4231 is for one permutation? For the requested 2 imho should get 4321 . / And it also seems to me that the task in its entirety (with 2 permutations) is also solved for a maximum of 2 full passes over the whole number, if in the auxiliary table of digits, in addition to their number, there are also indices of the last and the penultimate occurrence of the digit in the number are found when counting each digit on the first pass (of course, the code will be pretty awful) - avp
  • @avp: The correct answer is 4231 , not 4321 (there is an obvious example in the question) —In the question there is a restriction on exchange: you can only swap one pair of digits and that's it. If you want to get the largest number, then it would be enough for the largest to deduce (from the example in the answer) —it is even simpler (by code) the task would be. - jfs
  • Ohhh, I'm sorry! I read the question incorrectly. Not for 2 exchanges, but only 2 digits ( one exchange ). It radically simplifies everything (I already wanted to write a program, but now it’s not interesting,)) - avp