CODEWITHSUNDEEP
algorithmmapping
גלעד ברקן
גלעד ברקן

Reputation: 23945

How to create a one-to-one mapping from 3 digits to 3 completely different digits (base 10)?

How to create a one-to-one mapping from 3 digits to 3 completely different digits (base 10)?

Order matters. The given string has distinct digits.

For example, given 012, receive 345. The resultant string cannot contain a digit from the original. Mapping should be one-to-one for all 10 * 9 * 8 = 720 possibilities.

The few mathematical ideas I had, such as adding to or subtracting from the digits, all seem to allow for a digit to be repeated.

Upvotes: 4

Views: 119

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65508

Find the minimum k such that adding k to each digit mod 10 results in a disjoint set of digits. Do that. The inverse operation is subtracting the same k from each digit mod 10.

Proof sketch of correctness: all arithmetic operations are mod 10. The first observation is that there always exists a suitable k. There are 10 choices of k but only 9 possible conflicts, where a conflict consists of a position in the input and a position in the output that hold the same digit. Each conflict is triggered by exactly one choice of k. The second observation is that, given an input (a, b, c), the value of k is invariant across inputs (a + d, b + d, c + d) where d is a digit. It follows that the inverse operation truly is the inverse (because the value of k is determined to be the same) and hence that both operations are bijections.

Upvotes: 2

Related Questions