2

There is a sequence of such numbers that have unique digits but does not contain any 0 or 2. You are given a number N, find the next number in a sequence that is larger than N. If the number in a sequence is higher than 10e9, return -1

For example: given 2020, the answer is 3145, for 1982 the answer is 1983, for 9879 the answer is 13456

There is a similar problem: Given a number, find the next higher number which has the exact same set of digits as the original number. But, they are not same.

The algorithm complexity must be linear. The time limit is 1 second.

I have a brute-force solution, but it is not fast enough:

#include <iostream>
#include <vector>

using namespace std;


bool check_year(long year) {
    vector<int> counter(10);

    while(0 < year) {
        counter[year % 10] += 1;
        year = year / 10;
    }

    if(counter[0] > 0 or counter[2] > 0) {
        return false;
    }

    for(int i = 0; i < 10; i++) {
        if(counter[i] > 1) {
            return false;
        }
    }

    return true;
}

int main() {
    int year;
    cin >> year;

    for(long i = year; i < 10e9; i++) {
        if(check_year(i)) {
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;

    return 0;
}
maksadbek
  • 1,508
  • 2
  • 15
  • 28
  • a) you don't show your current solution or state what issue you are having with it b) are n and N the same, or what does n count? – Pete Kirkham Mar 18 '20 at 15:51
  • by `O(n)` I mean a linear time complexity, `n` and `N` are not the same. – maksadbek Mar 18 '20 at 15:52
  • Linear in what though? Your question only involves one number at a time, so it's not linear in terms of the size of input, and if it number has unique digits it can only be up to eight digits long, so even if it's 'linear in the number of digits' that is the same as O(8) so what is n? – Pete Kirkham Mar 18 '20 at 15:56
  • Okay, now I got you, I was wrong: `n` and `N` are the same, but the constant `c` must be 1/10. – maksadbek Mar 18 '20 at 15:59
  • @PeteKirkham I have updated the question and provided the time limit. It is 1 second. – maksadbek Mar 18 '20 at 16:01

2 Answers2

1

I've got an answer from Reddit: https://www.reddit.com/r/algorithms/comments/fkuy09/ideas_to_solve_this_problem/

It can be solved in O(9 * 1024 * 2 * 10) using dp: define a function "boolean F(integer i, bit-mask d, boolean f)" as whether or not an (i+1) digit number can be created using digits still unused (defined by unset bits in d) and which is also greater than the corresponding suffix of the target number if f is false (otherwise any such number). Actually getting the answer means just storing the minimum digit x at each position i such that F(i+1, d | 2x , f | (x > target[i] ) ) is true. The recurrences are also simple (in the code):

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000
int a[10];
int d;

int ndigits(int x)
{
  int ans = 0;
  while(x)
  {
      ans++;
      x = x/10;
  }
  return ans;
}

int fxp(int a, int b)
{
  if(b == 0) return 1;
  if(b == 1) return a;
  if(b%2) return a*fxp(a*a, b/2);
  return fxp(a*a, b/2);
}


int is_set1(int i, int d)
{
  if(d&fxp(2,i)) return 1;
  return 0;
}


int set1(int i, int d)
{
  d = d|fxp(2,i);
  return d;
}


int dp[10][1024][2];

int F(int i, int d, int f)
{
  if(i > 8) return INF;
  if(dp[i][d][f] != -1) return dp[i][d][f];

  if(i == 0)
  {
      int start = (f)?0:a[i] + 1; int j;
      for(j = start; j <= 9; j++)
          if(!is_set1(j, d) && j != 2 && j != 0) break;
      if(j == 10) { dp[i][d][f] = INF; return INF; };
      dp[i][d][f] = j; return j;
  }

  dp[i][d][f] = INF;
  int start = (f)?0:a[i];
  for(int x=start; x<=9; x++)
  {
      if(!is_set1(x, d) && x!=2 && x!=0)
      {
          int tf = ( f | (x > a[i]) );
          int t = F(i-1, set1(x, d), tf);
          if(t != INF) dp[i][d][f] = min(dp[i][d][f], x);
      }
  }
  return dp[i][d][f];
}

void the_print(int i, int d, int f)
{
  int x = dp[i][d][f];
  printf("%lld", x);
  if(i == 0) return; 

  int tf = (f | ( x > a[i]) );
  the_print(i-1, set1(x, d), tf);
}




#undef int
int main()
#define int long long
{

  for(int i=0; i<10; i++)
      for(int j=0; j<1024; j++)
          for(int k = 0; k<2; k++)
              dp[i][j][k] = -1;

  int z;
  scanf("%lld", &z);
  if(z == 0)
  {
      printf("1\n"); return 0;
  }
  for(int i=0; i<10; i++)
      a[i] = 0;
  int t = z, j = 0;
  while(t)
  {
      a[j] = t%10;
      t = t/10; 
      j++;
  }

  int b = F(ndigits(z)-1, 0, 0);
  if(b != INF)
  {
      the_print(ndigits(z)-1, 0, 0);
      printf("\n");
      return 0;
  }

  b = F(ndigits(z), 0, 0);
  if(b == INF)
      printf("-1");
  else
  {
      the_print(ndigits(z), 0, 0);
  }
  printf("\n");
  return 0;
}
maksadbek
  • 1,508
  • 2
  • 15
  • 28
0

I don't think there is need for dynamic programming.

For a number with d_i digits (d_0 to the left).

  • let out be the number with e_i digits
  • let used the set of digits already used (basically initialised with 0 and 2...)

for all i, starting from 0, we may

  • try to up d_i to available e_i (e_i > d_i and not in used). If we can, we are free to chose the e_j (j > i). Idem fillup the end of out with increasing digit not yet in used.
e.g
used = {3}
d_0 = 2
we can up d_0 to e_0 = 4 (since 3 is used)

used = {7,8,9}
d_0 = 6
we can't up d_0 since the only digits greater than 6 are already used (7,8,9)
  • or
    • if d_i is a dupe from the e_k (k < i), up it. If we can't then abort
e.g
used = {7}
d_2 = 7
d_2 is a dupe since used, we must up it. e_2 = 8
    • let d_i untouched (e_i == d_i) and go to i+1

In fine, we either up the i-th digit and return the number, or forward.

This makes 8 tests (one for each digit of input number)

const INVALID = 999999999
const concat = (s, d) => s === 0 ? d : parseInt('' + s + d, 10)
const add = (used, d) => new Set([...used]).add(d)
const tryUp = (used, d) => Array.from({ length: 10 - (d + 1) }, (_, i) => i + d + 1).find(d => !used.has(d))
const fillUp = (out, used, n) => {
  let last = -1
  for (let i = 0; i < n; ++i) {
    let up = tryUp(used, last)
    if (up === undefined) return INVALID
    last = up
    used = add(used, last)
    out = concat(out, last)
  }
  return out
}

function nextMin(digits, out, used, i) {
  if (i === digits.length) { return out }
  const d = digits[i]
  const up = tryUp(used, d)
  const okFwd = !used.has(d)
  // if it is the first digit and it is a 9, prepend with 1
  const specialCase = (i === 0 && d === 9) ? 
    nextMin([1].concat(digits.map(_ => 0)), out, used, i)
    : false
  if (!okFwd && !up && !specialCase) {
    return INVALID
  }
  const take = up ? fillUp(concat(out, up), add(used, up), digits.length - i -1) : INVALID
  const fwd = okFwd ? nextMin(digits, concat(out, d), add(used, d), i + 1) : INVALID
  return Math.min(specialCase ? specialCase : take, fwd)
}

const minYear = s => {
  const digits = s.split('').map(d => parseInt(d))
  const used = new Set([0, 2])
  const min = nextMin(digits, 0, used, 0)
  return min !== INVALID ? min : -1
}
console.log(minYear('2020'))
console.log(minYear('1982'))
console.log(minYear('9879'))
console.log(minYear('999'))
console.log(minYear('99999999'))
console.log(minYear('55666'))
grodzi
  • 5,633
  • 1
  • 15
  • 15