Tantangannya adalah untuk mengidentifikasi nomor yang hilang dalam serangkaian bilangan bulat yang tidak direvisi.

Anda diberi serangkaian digit (input yang valid akan cocok dengan ekspresi reguler ^[1-9][0-9]+$). String mewakili urutan bilangan bulat. Sebagai contoh 1234567891011,. Semua angka dalam urutan berada dalam kisaran dari 1dan 2147483647inklusif.

Urutan adalah serangkaian angka di mana setiap angka satu lebih besar dari pendahulunya. Namun, urutan ini dapat berisi satu dan hanya satu nomor yang hilang dari urutan tersebut. Ada kemungkinan bahwa string yang diberikan juga tidak mengandung angka yang hilang dari urutan. String akan selalu mengandung setidaknya dua angka dari urutan.

Kode harus menampilkan atau mengembalikan nilai yang hilang, atau 0(ini 0- bukan nilai yang salah) jika tidak ditemukan nilai yang hilang.

Berikut ini adalah input yang valid dan output / pengembaliannya:

input                         output    actual sequence (for refrence)
123467                        5         1 2 3 4 _ 6 7
911                           10        9 __ 11
123125126                     124       123 ___ 125 126
8632456863245786324598632460  8632458   8632456 8632457 _______ 8632459 8632460  
123                           0         1 2 3
8632456863245786324588632459  0         8632456 8632457 8632458 8632459  

Sementara semua ini digambarkan sebagai 'string' sebagai input, jika bahasa tersebut mampu menangani angka besar yang sewenang-wenang ( dcdan mathematica, saya melihat kalian berdua) input mungkin berupa angka besar yang sewenang-wenang alih-alih string jika itu membuat kode lebih mudah.

^{Untuk referensi, ini terinspirasi oleh pertanyaan Programmers.SE: Cari nomor yang hilang secara berurutan dalam string}

Haskell, 115 112 byte

g b|a<-[b!!0..last b]=last$0:[c|c<-a,b==filter(/=c)a]
maximum.map(g.map read.words.concat).mapM(\c->[[c],c:" "])

Baris pertama adalah definisi fungsi pembantu, yang kedua adalah fungsi anonim utama. Verifikasi kasus uji (saya harus menjalankan tes lebih pendek karena batasan waktu).

Penjelasan

Ini adalah solusi brute force: pisahkan string menjadi kata-kata dengan semua cara yang mungkin, parsing kata-kata menjadi bilangan bulat, lihat apakah itu rentang dengan satu elemen yang hilang (mengembalikan elemen itu, dan 0sebaliknya), dan ambil maksimum dari semua belahan. Pemeriksaan range-with-missing-element dilakukan dalam fungsi helper g, yang mengambil daftar bdan mengembalikan elemen tunggal dalam rentang [head of b..last of b]yang tidak ada b, atau 0jika tidak ada.

g b|                         -- Define g b
    a<-[b!!0..last b]=       -- (with a as the range [head of b..last of b]) as:
    last$0:[...]             --  the last element of this list, or 0 if it's empty:
            c|c<-a,          --   those elements c of a for which
            b==filter(/=c)a  --   removing c from a results in b.
mapM(\c->[[c],c:" "])        -- Main function: Replace each char c in input with "c" or "c "
map(...)                     -- For each resulting list of strings:
  g.map read.words.concat    --  concatenate, split at spaces, parse to list of ints, apply g
maximum                      -- Maximum of results (the missing element, if exists)

JavaScript (ES6), 117 byte

s=>eval(`for(i=l=0;s[i];)for(n=s.slice(x=i=m=0,++l);s[i]&&!x|!m;x=s.slice(x?i:i+=(n+"").length).search(++n))m=x?n:m`)

Penjelasan

Pendekatan yang cukup efisien. Selesai instan untuk semua kasus uji.

Mendapat masing-masing substring dari awal string input sebagai angka ndan initialises jumlah yang hilang muntuk 0. Ini kemudian berulang kali menghapus ndari awal string, menambah ndan mencari string untuknya. Jika index of n != 0, itu memeriksa m. Jika m == 0, setel m = ndan lanjutkan, jika tidak, ada beberapa nomor yang hilang, jadi berhentilah memeriksa dari substring ini. Proses ini berlanjut sampai seluruh string telah dihapus.

var solution =

s=>
  eval(`                     // use eval to use for loops without writing {} or return
    for(
      i=                     // i = index of next substring the check
      l=0;                   // l = length of initial substring n
      s[i];                  // if it completed successfully i would equal s.length
    )
      for(
        n=s.slice(           // n = current number to search for, initialise to subtring l
          x=                 // x = index of n relative to the end of the previous n
          i=                 // set i to the beginning of the string
          m=0,               // m = missing number, initialise to 0
          ++l                // increment initial substring length
        );
        s[i]&&               // stop if we have successfully reached the end of the string
        !x|!m;               // stop if there are multiple missing numbers
        x=                   // get index of ++n
          s.slice(           // search a substring that starts from the end of the previous
                             //     number so that we avoid matching numbers before here
            x?i:             // if the previous n was missing, don't increment i
            i+=(n+"").length // move i to the end of the previous number
          )
          .search(++n)       // increment n and search the substring for it's index
      )
        m=x?n:m              // if the previous number was missing, set m to it
  `)                         // implicit: return m

<input type="text" id="input" value="8632456863245786324598632460" />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>

JavaScript (ES6) 114

s=>eval("for(d=0,n=-9,z=s;z=z.slice((n+'').length);z.search(++n)?z.search(++n)?n=(z=s).slice(x=0,++d):x=n-1:0);x")  

Kurang bermain golf dan menjelaskan

f=s=>{
  d = 0  // initial digit number, will be increased to 1 at first loop 
  n = -9 // initial value, can not be found
  z = s  // initializa z to the whole input string
  // at each iteration, remove the first chars of z that are 'n' 
  // 'd' instead of 'length' would be shorter, but the length can change passing from 9 to 10 
  for(; z=z.slice((n+'').length); ) 
  {
    ++n; // n is the next number expected in sequence
    if (z.search(n) != 0)
    {
      // number not found at position 0
      // this could be the hole
      // try to find the next number
      ++n;
      if (z.search(n) != 0)
      {
        // nope, this is not the correct sequence, start again
        z = s; // start to look at the whole string again
        x = 0; // maybe I had a candidate result in xm but now must forget it
        ++d;   // try a sequence starting with a number with 1 more digit
        n = z.slice(0,d) // first number of sequence
      }
      else
      {
        // I found a hole, store a result in x but check the rest of the string
        x = n-1
      }
    }
  }      
  return x // if no hole found x is 0
}

Uji

F=s=>eval("for(d=0,n=-9,z=s;z=z.slice((n+'').length);z.search(++n)?z.search(++n)?n=(z=s).slice(x=0,++d):x=n-1:0);x")

console.log=x=>O.textContent+=x+'\n'

elab=x=>console.log(x+' -> '+F(x))

function test(){ elab(I.value) }

;['123467','911','123125126','8632456863245786324598632460',
  '123','124125127','8632456863245786324588632459']
.forEach(t=>elab(t))

<input id=I><button  onclick='test()'>Try your sequence</button>
<pre id=O></pre>

C, 183 168 166 163 byte

n,l,c,d,b[9];main(s,v,p)char**v,*p;{for(;s>1;)for(d=s=0,n=atoi(strncpy(b,p=v[1],++l)),p+=l;*p&&s<2;)p+=memcmp(p,b,c=sprintf(b,"%d",++n))?d=n,s++:c;printf("%d",d);}

Tidak disatukan

n,l,c,d,b[9];

main(s,v,p)char**v,*p;
{
    /* Start at length 1, counting upwards, while we haven't
       found a proper number of missing numbers (0 or 1) */
    for(;s>1;)
        /* Start at the beginning of the string, convert the
           first l chars to an integer... */
        for(d=s=0,n=atoi(strncpy(b,p=v[1],++l)),p+=l;*p&&s<2;)
            /* If the next number is missing, then skip, otherwise
               move forward in the string.... */
            p+=memcmp(p,b,c=sprintf(b,"%d",++n))?d=n,s++:c;

    printf("%d",d); /* print the missing number */
}