Interview puzzle: broken calculator

First part: Choose which k digits (out of 10 possible) are used in the result
With bit math (binomial coefficient) it is easy to calculate the number of different combinations of digits for a given k.
There are up to 252 choices (252 if k = 5, not so many).

If it is not clear what I am saying: for k = 2 there is 01,02,03,...09,12,13,...,19,23,24,...,89


No, for example. 11 because it's only 1, but k = 2 allows two different digits.
And no, for example. 90 because it's the same as 09, 91 = 19, etc.
The count of these possible combinations is 252 at k = 5, and it will not get bigger.

Finding all (up to) 252 possibilities for the current k
and iterating over them in a loop shouldn't be too hard.

For each opportunity, do the following:
{

Inside the loop, we have A, K, and the currently selected valid digits
to solve (the latter is of course different on each iteration of the loop)
Let's take A = 12899, K = 3, 123 digits as an example.
Now search for the first digit (left to right) that is not allowed.
In the example it would be 12 8 99 because 1 and 2 to the left of it are allowed.

Replace this (8) with the next least significant digit allowed (2) if there is one and replace everything to the right of it with the highest possible digit (3 too).
12899 => 12 3 99 => 123 33
Store the result 12333 somewhere in an array, etc.
If there was no next lowest possible digit, do nothing (nothing goes into the array)

(Correct addition with transfer introduces a new digit to the left of the changed one,
that is, disabled. A solution with this new digit will be found
when the loop comes to this digit)

Then the same thing again in the other direction:
Replace the found digit with the next higher possible one and everything is correct with the smallest one. This is also in the array, of
course, only if there was the next highest possible digit.
In the case of 12899, the only higher replacement for 8 would be 9,
but 9 is not possible (only 123).

}

After completing the entire loop (and each iteration has produced up to two new entries in the array), you have up to 502 possible solutions to the problem.
It remains only to check which one is the best (i.e. Calculate the difference to A for each record and take the solution, the minimum difference)

For K = 10, the solution is trivial. The difference is 0.

If the original number uses less than or equal to K single digit. The difference is 0. For example, 987777 5

use 3 different digits that are less than K (= 5).

For K = 1,

A number with length n will be associated with 999 ... 999 (n-digit) and 999 ... 999 ((n-1) -digit). This means 587 is bound by 999 and 99

. Hence the solution must be either an n-digit length number or 999 ... 999 ((n-1) -digit).

Let the leading digit of the number be a

(5 in 587), denote b=a+1

and c=a-1

. Compare the numbers with aaa...aaa

, bbb...bbb

, ccc...ccc

(the whole n-bit length). Note that this is just a test of no more than 2 of them.

• If original number = aaa...aaa
  
  , the difference is 0.
• If original number > aaa...aaa
  
  , keep comparing with bbb...bbb
  
  .
• If original number < aaa...aaa
  
  , keep comparing with ccc...ccc
  
  .

Rule for K = 1, if b=10

, ignore bbb...bbb

, since aaa...aaa = 999...999

, upper bound. if c=0

, change ccc...ccc

to 999...999

((n-1) -digit) to check the lower bound, for example10000 1 -> 9999

For K in the range [2.9], note that first K-1 distinct digit from left to right must be used

. For example, in this case it is necessary to use 9988898988981234 3

, 2 figures 8 and 9.

Evidence:

Fact:

• Number of individual digits in original number> K
• K-1! = 0

We can always form two values z000...000

and z999...999

by using K a different digit where z

is the form over K-1 different digit ( z = 998889898898

in the example above) and assign the K th digit as 0 or 9 (ignore the fact that 0 or 9 can be used K-1

as not important)

With z000...000

and z999...999

( 9988898988980000

and 9988898988989999

) the optimal solution is associated with two values. If z changes to z + 1 or z-1, the difference will increase, which doesn't make sense. Thus, the z part will always be used and first K-1 distinct digit from left to right must be used

.

End of proof

At the first meeting of K-th separate numbers (leading figure on the right after the z-often referred to as t

), you can consider three possible cases t

, t+1

and t-1

.

Let's start with t

. Usage t

will use the entire K digit, so no digit can be assigned. Keep checking the digit on the right side until we come across a digit that is not in those significant K digits. This time we choose no more than two. The closest digit in K that is greater than the encounter digit and the closest digit in K that is less than the encounter digit. Using the larger nearest digit in K will result in a quantity larger than the original number, so the remaining digit should be minimized by choosing the smallest digit in K. Similarly, the remaining digit for the smaller nearest digit in the case of K will be the largest digit in K.

In case t+1

it only needs to be checked if there is no larger nearest digit in K in case t

. Usage t+1

will always be greater than the original number, we need to minimize the remaining digit. Note that there t+1

may be one of the digits in K-1, we have a free digit and therefore include 0

(if 0

not in K-1). We can then select the smallest digit in K (or K-1 if t+1

u 0

are in K-1

) for the remaining digit.

In the case t-1

it is only necessary to check when there is no less than the nearest digit in K in the case t

. Usage t-1

will always be less than the original, we need to maximize the remaining figure. Note that there t-1

may be one of the digits in K-1, we have a free digit, and therefore include 9

(if 9

not in K-1). We can then select the largest digit in K (or K-1 if t-1

u 9

are in K-1

) for the remaining digit.

The solution time is O (len (A)). Find min | A - B |, with a different number of K from K. First, to remove abs, we must find B1 with the condition (min (Bi | Bi> = A, with a different number of digits),

• Let A = a1a2 ... an, B1 = b1b2 ... bn, find the longest sequence that ai = bi, until the different number exceeds K. Suppose that a1-> aj = b1-> bj

• If j == n, then B1 = A

• From the set {a1, a2, ..., aj}, we find the minimum number greater than b [j + 1]

If we find ak (1 <= k <= j), then let b [j + 1] = ak, and the rest of b [j + 1] → bn is filled with min {a1, a2, ..., a;}

If not, we change bj from aj to a [j] +1. For the rest b [j + 1] → bn,

If [j] +1 is in the set {a1, a2, ..., aj-1}, that means we can still press one digit, we choose 0 as the complement. b [j + 1] → bn are filled with 0.

If a [j] +1 is not in the set {a1, a2, ..., aj-1}, choose min {a1, a2, ..., aj-1, a [j] +1} as the value, which is filled with b [j + 1] → bn

Similarity, we can find the closest B2 number that is less than A,

After that we just compare B1-A with A-B2, choose the minimum.

Following the C ++ code:

    #include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <sstream>
using namespace std;

string target_num;
string up_num;
string down_num;
int K;

bool hash_key[10];
bool hash_copy[10];

int find_closet_k(int c, bool up) {
 int i = c;
 while(true) {
  if (hash_key[i]) {
   return i;
  }

  if(up) {
   ++i;
   if (10 <= i) {
    break;
   }
  } else {
   --i;
   if (i < 0) {
    break;
   }
  }

 }
 return -1;
}

char min_k() {
 for (int i = 0; i < 10; ++i) {
  if (hash_key[i]) {
   return '0' + i;
  }
 }
}

char max_k() {
 for (int i = 9; 0 <= i; --i) {
  if (hash_key[i]) {
   return '0' + i;
  }
 }
}

bool is_head_zero(int v, string num,int end_pos) {
 if (0 == v) {
  for (int i = 0; i < end_pos; ++i) {
   if (num[i] != '0') {
    return false;
   }
  }
  return true;
 }
 return false;
}

int string2int(string s) {
 std::stringstream ss;
 ss << s;
 int is;
 ss >> is;
 return is;
}

void find_closest() {
 int k = 0;
 int i = 0;
 for (i = 0; i < target_num.size(); ++i) {
  int c = target_num[i] - '0';
  if (!hash_key[c]) {
   if (k == K) {
    break;
   }
   hash_key[c] = true;
   ++k;
  }
  up_num.push_back(target_num[i]);
  down_num.push_back(target_num[i]);
 }

 if (i == target_num.size()) {
  printf("0\n");
  return;
 }

 copy(hash_key, hash_key + 10, hash_copy);
 int j = i - 1;
 up_num.resize(target_num.size());
 int c = target_num[j + 1] - '0';
 int v = find_closet_k(c, true);
 if (v == -1) {
  int aj = target_num[j] - '0';
  up_num[j] = aj + 1 + '0';
  if (hash_key[aj + 1]) {
   //only used K - 1, use 0 as min_k();
   fill(up_num.begin() + j + 1, up_num.end(), '0');
  } else {
   hash_key[aj] = false;
   hash_key[aj + 1] = true;
   fill(up_num.begin() + j + 1, up_num.end(), min_k());
  }
 } else {
  up_num[j + 1] = v + '0';
  fill(up_num.begin() + j + 1, up_num.end(), min_k());
 }

 copy(hash_copy, hash_copy + 10, hash_key);
 j = i - 1;
 down_num.resize(target_num.size());
 v = find_closet_k(c, false);
 if (v == -1) {
  int aj = target_num[j] - '0';
  down_num[j] = aj - 1 + '0';
  if (hash_key[aj - 1] || is_head_zero(aj - 1,down_num, j)) {
   fill(down_num.begin() + j + 1, down_num.end(), '9');
  } else {
   hash_key[aj] = false;
   hash_key[aj -1] = true;
   fill(down_num.begin() + j + 1, down_num.end(), max_k());
  }
 } else {
  down_num[j + 1] = v + '0';
  fill(down_num.begin() + j + 1, down_num.end(), max_k());
 }

 unsigned __int64 upi;
 unsigned __int64 targeti;
 unsigned __int64 downi;
 sscanf(up_num.c_str(), "%lld", &upi);
 sscanf(target_num.c_str(),"%lld",&targeti);
 sscanf(down_num.c_str(),"%lld",&downi);

 unsigned __int64 delta = min(upi - targeti, targeti - downi);
 printf("%lld\n", delta);

}

int main(){
 while (true) {
  cin>>target_num>>K;
  fill(hash_key, hash_key + 10, false);
  find_closest();
  up_num.clear();
  down_num.clear();
  target_num.clear();
 }

}