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. 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;
}

• SuperBiasedMan: Welcome to Code Review! I have rolled back the last edit. Please see what you may and may not do after receiving answers .

Answer 1

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();
}

• Deduplicator: I would only use a single vector, but otherwise good work.

Answer 2

Well, there's lots to improve about your program.

1. Consider adopting any of the common styles for code-formatting.
   As-is, your current formatting seriously impedes readability.

2. #include <bits/stdc++.h> is a bad idea, sharply limiting portability and 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 "
 "[phone]. 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;
}

• 200_success: You used recursion in luckydiv_helper(), and the task forbids recursion.
• Deduplicator: @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.

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);
 }
 }
}

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.