FastPrep
Problem · Greedy

Minimize Difference Between Two Numbers

Learn this problem
● HardMicrosoftINTERNOA
See Microsoft hiring insights

Problem statement

In this task you are given two strings of digits that represent (possibly very large) integers. Your goal is to make those numbers as close to one another as possible. In other words, you want to minimize the absolute value of their difference. You can swap some of the corresponding digits (e.g. the first digit of the first number with the first digit of the second number, the second digit of the first number with the second digit of the second number, etc.). Swapping the digits is an extremely tiring task, so you want to make as few swaps as possible.

Given two strings S and T, both of length N, returns the minimum number of swaps needed to minimize the difference between the two numbers represented by the input strings.

Write an efficient algorithm for the following assumptions:

  • lengths of S and T are equal and within the range [1..100,000];
  • S and T consist only of digits and no other characters;
  • neither S nor T contain leading zeroes.

    • Function

    minimizeDifference(S: String, T: String) → int

    Examples

    Example 1

    S = "29162"T = "10524"return = 2

    We can swap the second and the fourth digits and obtain "20122" and "19564". The difference between the numbers is 558 and the number of swaps is 2. One can easily check that the difference is the smallest possible. Note that we could obtain the same difference by swapping the first, third and fifth digits, but this solution requires three swaps.

    Constraints

    ..

    More Microsoft problems

    drafts saved locally
    public int minimizeDifference(String S, String T) {
  // Write your code here
}
    S"29162"
    T"10524"
    expected2
    checking account