# Algorithm to add all lucky numbers under [N] to a Vector

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. I need to check if a given number is evenly divisible by any lucky number or 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 separate 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=10;number<100;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.

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.

The Program

#include <bits/stdc++.h>
using namespace std;

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

//This Part Needs to be Optimised
vector<int>lucky;
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=10;number<100;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
//This Part Needs to be Optimised

int flag=0;
for(unsigned int index=0;index<lucky.size();index++)
{
if(in_num%lucky[index]==0) {flag=1; break;}
}
if(flag==1) {cout<<"YES";}
else {cout<<"NO";}
return 0;
}


It is fairly straightforward to generate a vector with all the values. First, you should treat all the same length numbers as a group. The values 4 and 7 would be in a singledigit vector. To get the twodigit vector, simply go through the previous vector, multiplying each by 10 and then adding 4 to push back a value and add 7 to push back another value.

vector<int> lucky;
vector<int> current;
vector<int> next;
current.push_back(4);
current.push_back(7);
lucky.push_back(4);
lucky.push_back(7);
int value=0;
while(value < N)
{
for(unsigned int i=0;i<current.size();++i)
{
value=current[i]*10+4;
next.push_back(value);
lucky.push_back(value);
value=current[i]*10+7;
next.push_back(value);
lucky.push_back(value);
}

current=next;
next.clear();
}

• I would only use a single vector, but otherwise good work. – Deduplicator Nov 13 '15 at 0:19

1. Consider adopting any of the common styles for code-formatting.

2. #include <bits/stdc++.h> is a bad idea, sharply limiting portability ad increasing compile-times. See: How does #include <bits/stdc++.h> work in C++?
Just include those headers you need, which are <vector> and <iostream>.

3. You are courting conflicting symbols and general bafflement with any minor change of your toolchain. See: Why is using namespace std; considered bad practice?

4. You are using the popular for-if-antipattern. See Introducing the for-if anti-pattern
Why don't you just enumerate the ones you are actually interested in?

5. A for-range-loop is simpler than explicitly using iterators/indices. Unless you actually need them.

6. In the end you don't actually want that whole list, only whether one of them divides your input-number. So why store them at all, and why also those bigger than the input-number?

7. return 0; is implicit for main in C++.

Doing it as it should be done, with recursion on coliru:

#include <stdio.h>

int luckydiv_helper(long in, long num, int free) {
return !free
? !(in % num)
: luckydiv_helper(in, 10 * num + 4, free - 1)
|| luckydiv_helper(in, 10 * num + 7, free - 1);
}

int luckydiv(long in) {
long abort = in;
for(int digits = 1; abort; digits++, abort /= 10)
if(luckydiv_helper(in, 0, digits))
return 1;
return !in;
}

int main() {
long in;
if(scanf("%ld", &in) != 1 || in < -999999999 || in > 999999999) {
fprintf(stderr, "You didn't enter a number between -999999999 and "
"+999999999. Aborting.\n");
// A long can represent all 9-digit decimal numbers.
return 1;
}
printf("%ld ", in);
if(in < 0) in = -in;
puts(luckydiv(in) ? "YES" : "NO");
}


A way to efficiently get all "lucky" numbers without recursion:

#include <limits>
#include <vector>

template<class T> std::vector<T> luckyvector() {
std::vector<T> v = {4, 7};
const auto limit4 = (std::numeric_limits<T>::max() - 4) / 10;
const auto limit7 = (std::numeric_limits<T>::max() - 7) / 10;
T x;
for(size_t i = 0; (x = v[i]) <= limit7; i++) {
v.push_back(x * 10 + 4);
v.push_back(x * 10 + 7);
}
if(x <= limit4)
v.push_pack(x * 10 + 4);
return v;
}

• You used recursion in luckydiv_helper(), and the task forbids recursion. – 200_success Nov 13 '15 at 0:52
• @200_success: I gave a way to do the task the program solves efficiently with recursion, yes. And a way to just generate a vector with all those numbers, without recursion. Clarified what is what. – Deduplicator Nov 13 '15 at 1:06
#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);
}
}
}


Even though I am still using the for-if anti-pattern as Deduplicator pointed out, I was finally able to make the is_lucky function which maybe less efficient and a lesser intelligent way to do it than the other ones posted, seems to be the shortest way to do the task.