govind53's blog

Minimum number of swaps needed to reduce absolute difference between integer strings
By govind53, history, 6 months ago, In English

Need help with figuring out best possible solution for this problem: There are two strings of same length representing numbers, we can swap the elements at corresponding index in both strings. There exist some integer k such that k swaps results in strings with minimum absolute difference. Task is to find k. Example of one of possible swap: s = "123" and t = "456" -> swap at index 0 makes s = "423" and t = "156" -> abs diff is 267 a possible solution is using back tracking but there should be better solution for this.

A follow-up question, given some k we want to find minimum possible absolute difference after k swaps.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wouldn't it just be: For index 0: Put the bigger number s[0],t[0] in s, smaller one in t For every other index: Put the smaller number s[i],t[i] in s, bigger one in t

Please correct me if I'm wrong!

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For the first question:

So we can get this method:

  1. When $$$s_0 > t_0$$$, swap $$$s_0, t_0$$$, add $$$1$$$ to $$$k$$$.

  2. for each positive integer $$$i$$$(assume $$$s_i$$$ and $$$t_i$$$ exists), when $$$s_i < t_i$$$ swap $$$s_i, t_i$$$, add $$$1$$$ to $$$k$$$.

UPD: The solution of the second question:

This is pretty similar to the solution of the first question, but when $$$a_0 > t_0$$$, we swap $$$s$$$, $$$t$$$, and except this we can do at most $$$k$$$ swaps, so we swap the digits from front to back.

And when there is some extra swaps, use these swaps on the last digit.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the k which will come would be minnimum or not

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When just use this method, we cannot guarantee that $$$k$$$ is th minimum.

      But replace the 1. with "When $$$s_0 > t_0$$$, swap $$$s, t$$$.", the $$$k$$$ will be minimum.

      → Reply
»
9 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you / anyone please add the question link ? I got the same during an interview.

→ Reply
»
8 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
#include <bits/stdc++.h>

using namespace std;

/*
consider s = "[a1][a2][a3]...", t = "[b1][b2][b3]..."
then the diff can be represented as 
 
exp = (a1-b1) * 10^x + (a2-b2) * 10^x-1....

abs_diff = |exp|, which we want to minimize

if (a1-b1) is even +1...we can afford to have (ai-bi) = -9 for all other i's & still the expression exp will never be negative

[Please help me with the question link..need to test my solution]

*/

int solve(const string & s,
  const string & t) {
  bool sw = s[0] > t[0];
  int cnt = 0;
  int n = s.size();
  for (int k = 1; k < n; ++k) {
    cnt += s[k] != t[k] && (!(sw ^ (s[k] > t[k])));
  }
  return cnt;
}

int main() {
  string s = "29162", t = "10524";
  cout << solve(s, t);
  return 0;
}
→ Reply