[R] Lowest number in a numeric string

[Petr Savicky]

On Thu, Jun 14, 2012 at 01:08:53AM -0700, mogwai84 wrote:
> Hi all,
> 
> I've got a very long numeric string. I want to find the lowest number that
> isn't in that string.
> 
> E.G
> 
> String = 123456
> Therefore 7 is the lowest number not in that string
> 
> E.G.2
> 
> String = 1234567891011
> Therefore 13 is the lowest number not in that string.

Hi.

Try the following.

  s <- "1234567891011"
  n <- nchar(s)
  x <- rep(NA, times=choose(n+1, 2))
  k <- 0
  for (i in 1:n) {
      for (j in i:n) {
          k <- k + 1
          x[k] <- as.numeric(substr(s, i, j))
      }
  }
  for (i in 1:1000) {
      if (! i %in% x) break
  }
  print(i)

  [1] 13

For a longer string, we may use the fact that the number of the numbers included
in the string is at most choose(n+1, 2). This implies that the lowest missing
number is at most choose(n+1, 2) + 1. Due to this, we can consider only
sequencies of digits of length at most ceiling(log10(choose(n+1, 2) + 1)).

Hope this helps.

Petr Savicky.