Algorithm to add all lucky numbers under [N] to a vector?

Question

A lucky number is defined as a positive integer whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Now, suppose I want to add all Lucky Numbers under a given integer [N] to a vector, without using recursion. For the sake of simplicity, let N = 1000.

I came up with an approach to just check each digit of all the numbers under [N] by making seperate loops for 1 digit numbers, 2 digit numbers etc.

for(int number=0;number<10;number++) {if(((number%10==4)||(number%10==7))) {lucky.push_back(number);}} //1 Digit Lucky Numbers
for(int number=10;number<100;number++) {if(((number%10==4)||(number%10==7))&&(((number/10)%10==7)||((number/10)%10==4))) {lucky.push_back(number);}} //2 Digit Lucky Numbers
for(int number=100;number<1000;number++) {if(((number%10==4)||(number%10==7))&&(((number/10)%10==7)||((number/10)%10==4))&&(((number/100)%10==7)||((number/100)%10==4))) {lucky.push_back(number);}} //3 Digit Lucky Numbers
for(int number=1000;number<10000;number++) {if(((number%10==4)||(number%10==7))&&(((number/10)%10==7)||((number/10)%10==4))&&(((number/100)%10==7)||((number/100)%10==4))&&(((number/1000)%10==7)||((number/1000)%10==4))) {lucky.push_back(number);}} //4 Digit Lucky Numbers

I was thinking that this could roughly be converted to something along these lines but I am not quite able to come up with what exactly to do.

for(number;number<10*itr_counter;number++)
    {
    if(((number%10*itr_counter==4)||(number%10*itr_counter==7))) {lucky.push_back(number);}
    itr_counter*=10;
    }

I basically want to check each digit of all 1 digit numbers by taking modulo 10 and checking if the digits are 4 or 7. Similarly for a number consisting of X digits, I am taking modulo and dividing the number by 10, 100 and so on to check against 4 or 7.

Is this a good approach to the said problem? Also, can someone help me optimise the first block of code into something smaller and more efficient? Something along the lines of the second block of code would work.

Answer 1

The solution similar to the Sieve of Eratosthenes works, but it far from being smart.

Consider putting every value in a ordered vector: the n-th element is going to be composed of one of the previous elements plus a final '4' o '7'. Keeping this in mind you can generate the numbers and not check for them.

Here's the idea

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define MAX_NUMBER 1000

int main()
{
    std::vector<int> lucky_numbers(0);

    if (lucky_numbers.size () == 0)
    {
        if (4 < MAX_NUMBER)
            lucky_numbers.push_back (4);
        if (7 < MAX_NUMBER)
            lucky_numbers.push_back (7);
    }

    bool exit = false;

    while (!exit)
    {
        int size = lucky_numbers.size ();

        for (int i = 0 ; i < size ; i++)
        {
            int new_lucky_number = lucky_numbers[i] * 10 + 4;
            if (new_lucky_number < MAX_NUMBER &&
                std::find(lucky_numbers.begin(), lucky_numbers.end(), new_lucky_number) == lucky_numbers.end() )
            {
                lucky_numbers.push_back (new_lucky_number);
            }
            else if (new_lucky_number >= MAX_NUMBER)
            {
                exit = true;
                break;
            }

            new_lucky_number = lucky_numbers[i] * 10 + 7;
            if (new_lucky_number < MAX_NUMBER &&
                std::find(lucky_numbers.begin(), lucky_numbers.end(), new_lucky_number) == lucky_numbers.end() )
            {
                lucky_numbers.push_back (new_lucky_number);
            }
            else if (new_lucky_number >= MAX_NUMBER)
            {
                exit = true;
                break;
            }
        }
    }

    int size = lucky_numbers.size ();

    for (int i = 0 ; i < size ; i++)
        std::cout << lucky_numbers[i] << std::endl;
}

Depending on the conditions of your problem, you can optimize out the use of std::find and make it even faster.

Update

After discussing the solution, here's the enhanced version. The checks are stille inline, but avoids the find the restarts.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define MAX_NUMBER 1000

int main()
{
    std::vector<int> lucky_numbers(0);
    std::vector<int>::iterator it;

    if (lucky_numbers.size () == 0)
    {
        if (4 < MAX_NUMBER)
            lucky_numbers.push_back (4);
        if (7 < MAX_NUMBER)
            lucky_numbers.push_back (7);
    }

    for (int i = 0 ; ; i++)
    {
        int new_lucky_number = lucky_numbers[i] * 10 + 4;

        if (new_lucky_number < MAX_NUMBER)
            lucky_numbers.push_back (new_lucky_number);
        else
            break;

        new_lucky_number = lucky_numbers[i] * 10 + 7;

        if (new_lucky_number < MAX_NUMBER)
            lucky_numbers.push_back (new_lucky_number);
        else
            break;
    }

    for (int i = 0 ; i < lucky_numbers.size () ; i++)
        std::cout << lucky_numbers[i] << std::endl;
}

Answer 2

This answer takes the idea from the answer by Ottavio Campana but demonstrates a principle of good software engineering, which is keep each distinct element of the work and each element of the design decisions in a single place in the code (see my comments on that earlier answer):

// Anywhere a type is a design decision, rather than an obvious choice, use a typedef
typedef unsigned long long number;
typedef std::vector<number> container;

// A function is usually the best way to centralize work.
// If the parameter passing cost exceeds the work, use an inline function
// and rely on the optimizer to sort it out
inline bool push_number(container& c, number n, number m)
{
   if (n>m) return false;
   c.push_back(n);
   return true;
}

...

number n=0;
unsigned i=0;
container c;
while ( push_number(c,n+4,MAX_NUMBER) && push_number(c,n+7, MAX_NUMBER) )
{
   n = 10 * c[i++];
}

Notice that the > operation in comparing to max appears ONCE in the code. The 4 and 7 each appear ONCE in the code. The multiply by 10 appears ONCE in the code.

As you get into more complicated problems, the extra effort to organize so such things each appear once becomes the biggest difference between sloppy programming and real software engineering.

If MAX_NUMBER came from a #define or any global place, then passing it twice makes much less sense than just directly using it inside the function. But I object to #define for such things and object to globals nearly as much. So I didn't want to code in the assumption that the max number is globally visible. Passing it isn't good, but it isn't really bad. In a real project, when you find yourself excessively passing things like c and MAX_NUMBER that is a hint that the work should be done by member functions of a class that has those things as member variables.

Answer 3

#include <iostream>
#include <vector>

bool is_lucky(int check_num)
{
while(check_num!=0)
    {
    if((check_num%10!=4)&&(check_num%10!=7))
        {
        return false;
        }
    check_num/=10;
    }
return true;
}

int main()
{
std::vector <long long> lucky;
for(int in_num=1;in_num<1000;in_num++)
    {
    if(is_lucky(in_num))
        {
        lucky.push_back(in_num);
        }
    }
}

I was finally able to make this is_lucky function which still isn't the most efficient way to do the task, but seems to be shortest way to do the task.

Answer 4

// Use a D bit number as a proxy for a D digit number
// Then use L=2^D as a proxy for D in a loop through required values of D
// Notice D is only implied, we don't need to actually store it.
for (unsigned L=2; ; L*=2)
{
   // Loop through all D bit numbers (which happen to be all numbers less than L
   for (unsigned N=0; N<L; ++N)
   {
      // Convert that D bit number into a D digit number
      unsigned long long X = 0;
      // Loop through the bits of N converting to digits
      for ( unsigned B=L; (B>>=1)>0; )
      {
         X = X * 10 + 4;
         if ( B & N ) X += 3;  // change the 4 to a 7.
      }
      if ( X > MAX_NUMBER )
         return;  // break out of two levels of loop
      lucky.push_back( X );
   }
}

That may look excessively tricky for such a simple task. But if MAX_NUMBER were seriously large, this approach is far better than testing whether numbers are "lucky".

Also notice this methods finishes (detects completion) at an awkward point in the flow of the code (inside two levels of loop). In serious programming that kind of thing is pretty common. My overwhelming preference in that situation is to put the entire nested loop into a function so that I can use return from the function as an easy way to break two levels of loop. Structured programming fanatics may be highly offended by that use of return. You can accomplish the same flow control by mixing a done flag into the control of each loop. That approach offends me as much as this return offends a structured programming fanatic.

A bit more detail on the two tricky loops:

Conceptually we have D and we want it to start at 1 and count up until we hit the return instruction and we want to compute L=1<<D meaning the number whose only set bit is in position D. But instead we skip D entirely and compute L directly.

Then we want the inner-most loop to have a bit number E and conceptually count down the bit positions below D:

for (E=D-1; E>=0; --E)

And we want to similarly compute B=1<<E as the number whose only set bit is in position E. But again we don't have D and we don't need E, we can compute B directly.

Answer 5

As you are not parsing a list verifying that the numbers are lucky numbers, you are much better off building the list/vector of lucky numbers using a function.

One way to approach this is to count in binary from 0 to the given digits you're aiming for. For n=1000 that would be to 0b111 = 7, and then replace each 0 with a 4, and each 1 with a 7. i.e. 0b101 = 747. Then you can easily sum up the resulting vector.

Regarding your iterative approach of verifying it as a lucky number I would make a function something like the following in pseduocode:

while number > 0:
   lastDigit = number % 10
   if lastDigit != 4 and lastDigit != 7
       return false
   number = number / 10

return true

Answer 6

Considering you aren't scanning a list to find lucky numbers in a set, instead you're generating a list of all the possible combinations of numbers between 0 and N that contain those digits; Wouldn't it be more efficient to simply generate all lucky numbers using a simple function?

Answer 7

Maybe you could make a scatterplot graphic and use Gradient descendant algorithm and a machine learning for estimate your values ?