### govind53's blog

By govind53, history, 3 weeks ago,

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.

• +1

 » 3 weeks ago, # |   0 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 tPlease correct me if I'm wrong!
 » 3 weeks ago, # | ← Rev. 2 →   0 For the first question:So we can get this method: When $s_0 > t_0$, swap $s_0, t_0$, add $1$ to $k$. 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.
•  » » 3 weeks ago, # ^ |   0 the k which will come would be minnimum or not
•  » » » 3 weeks ago, # ^ |   0 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.