How do I find numbers that contain the sequence 666?

Not A Homework Question, We Are Still Studying Loops At School encountered in a programming challenge ... Start The number 666 is considered to be the occult "number of the beast" and is a well used number in all major apocalypse themed blockbuster movies. However the number 666 can't always be used in the script so numbers such as 1666 are used instead. Let us call the numbers containing at least three contiguous sixes beastly numbers. The first few beastly numbers are 666, 1666, 2666, 3666, 4666, 5666...

Given a 1-based index n, my program should return the nth beastly number.

Definition

• Class: ApocalypseSomeday
• Method: getNth
  • Parameters: int
  • Returns: int
  • Method signature: int getNth(int n) (be sure your method is public)

Constraints

• n will be between 1 a开发者_高级运维nd 10000, inclusive

Examples

1. 2 returns: 1666
2. 3 returns: 2666
3. 6 returns: 5666
4. 187 returns: 66666
5. 500 returns: 166699

Not a problem given by a teacher. I found it in a programming challenge C++. My progress so far

public class ApocalypseSomeday
{
  public int getNth(int n)
  {
       int i = 0, j = 0,k = 0;
       int s = 1,c = 1;
       int r = 666;
       while (s < n)
       {
            k = 0;
            while ((c % 10000) == 6666 && s < n && k < 10000)
            {
                r = c * 10000 - 6000 + k;
                k++;
                s++;
            }

Since there are no performance constraints mentioned and the size of the input is quite small, the simplest option is to use brute force: count from 1 upwards and check each number to see if it contains 666. When you find n such numbers, return the last one you found.

The simplest (but slow) way to check if a number contains 666 is to convert it to a string and search for the substring '666'. Again, because of the limited size of the input and lack of performance constraints, this should be sufficient.

It is probably faster to make this check using arithmetic operations. In Python you could do it like this:

def contains666(x):
    while x >= 666:
        if x % 1000 == 666:
            return True
        x /= 10
    return False

If you need your program to be as fast as possible you could precalculate the answer for each possible value of n and hardcode the answer into your program. Then you can find the result for any n with a simple indexing operation.

public class ApocalypseSomeday {
     public int getNth(int n) {
          int i = 0, j = 0,k = 0;
          int s = 1,c = 1;
          int r = 666;
          while (s < n) {
               k = 0;
               while ((c % 10000) == 6666 && s < n && k < 10000) {
                   r = c * 10000 - 6000 + k;
                   k++;
                   s++;
               }
               if (s == n) return r;
               if (k == 10000) {
                   c++;
                   continue;
               }
               k = 0;
               while ((c % 1000) == 666 && s < n && k < 1000) {
                   r = c * 1000 + k;
                   k++;
                   s++;
               }
               if (s == n) return r;
               if (k == 1000) {
                   c++;
                   continue;
               }
               k = 0;
               while ((c % 100) == 66 && s < n && k < 100) {
                   r = c * 1000 + 600 + k;
                   k++;
                   s++;
               }
               if (s == n) return r;
               if (k == 100) {
                   c++;
                   continue;
               }
               k = 0;
               while ((c % 10) == 6 && s < n && k < 10) {
                   r = c * 1000 + 660 + k;
                   k++;
                   s++;
               }
               if (s == n) return r;
               if (k == 10) {
                   c++;
                   continue;
               }
               r = c * 1000 + 666;
               c++;
               s++;
          }
          return r;
     }
}

class ApocalypseSomeday
{
public:
int getNth(int n)
{
    int cpt = 0;
    int nbr = 666;
    while (cpt != n)
    {
        if (((nbr % 1000) == 666) )
        {
            //printf("nb[%d]:%d\n", cpt, nbr);
            cpt++;
            nbr++;
            continue;
        }
        if ((nbr % 10000) - (nbr % 10) == 6660)
        {
            //printf("nb[%d]:%d\n", cpt, nbr);
            cpt++;
            nbr++;
            continue;
        }
        if ((nbr % 100000) - (nbr % 100) == 66600)
        {
            //printf("nb[%d]:%d\n", cpt, nbr);
            cpt++;
            nbr++;
            continue;
        }
        nbr++;
    }
    return nbr-1;
}

};