find the minimum lucky number that has the sum of digits equal to N

Question

The lucky numbers are the positive integers whose decimal representations contain only the digits 4 or 7 .enter code here` For example, numbers 47 , 474 , 4 are lucky and 3 , 13 , 567 are not if there is no such no then output should -1. input is sum of digits. i have written this code:

int main(){
long long int s,no=0,minimum=999999999999999999999;
cin>>s;

for(int i=0; i<=s; i++){
    for(int j=0; j<=s; j++){
        if(i*4+j*7==s){no=0;
            for(int k=0; k<i; k++){
                    no=no*10+4;
            }
                for(int l=0; l<j; l++){
                    no=no*10+7;
                }if(no<minimum){
                minimum=no;}
        }
    }
}if(minimum==999999999999999999999){cout<<-1;}
else {cout<<minimum;}
}

it is working fine smaller sum values but input is large then no formed is large due to which i am not able to compare them, the constraints for sum is 1<=n<=10^6

Answer 1

This answer shows a process, one of refinement to develop an efficient solution. The most efficient answer can be found in the paragraphs at the bottom, starting with the text "Of course, you can be even more clever ...".

I've left the entire process in so you can understand the sort of thinking that goes into algorithm development. So, let's begin.

---

First, I wouldn't, in this case, try to compare large numbers, it's totally unnecessary and limits the sort of ranges you want to handle. Instead, you simply have some number of fours and some number of sevens, which you can easily turn into a sum with:

sum = numFours * 4 + numSevens * 7

In addition, realising that the smallest number is, first and foremost, the one with the least number of digits, you want the absolute minimum number of fours and maximum number of sevens. So start with no fours and as many sevens as needed until you're at or just beyond the required sum.

Then, as long as you're not at the sum, perform the following mutually exclusive steps:

• If you're over the desired sum, take away a seven if possible. If there are no sevens to take away, you're done, and there's no solution. Log that fact and exit.
• Otherwise (i.e., if you're under the sum), add a four.

At this point, you will have a solution (no solution possible means that you would have already performed an exit in the first bullet point above).

Hence you now have a count of the fours and sevens that sum to the desired number, so the lowest number will be the one with all the fours at the left (for example 447 is less than any of {474, 744}). Output that, and you're done.

By doing it this way, the limitation (say, for example, an unsigned 32-bit int) is no longer the number you use (about four billion, so nine digits), instead it is whatever number of fours you can hold in four billion (about a billion digits).

That's an increase of about 11 billion percent, hopefully enough of an improvement for you, well beyond the 106 maximum sum specified.

In reality, you won't get that many fours since any group of seven fours can always be replaced with four sevens, giving a smaller number (a7777b will always be less than a4444444b, where a is zero or more fours and b is zero or more sevens, same counts in both numbers), so the maximum count of fours will always be six.

---

Here's some pseudo-code (Python code, actually) to show it in action. I've chosen Python, even though you stated C++, for the following reasons:

• This is almost certainly an educational question (there's very little call for this sort of program in the real world). That means you're better off doing the heavy lifting of writing the code yourself, to ensure you understand and also to ensure you don't fail for just copying code off the net.
• Python is the most awesome pseudo-code language ever. It can easily read like normal English pseudo-code but has the added benefit that a computer can actually run it for testing and validation purposes :-)

The Python code is:

import sys

# Get desired sum from command line, with default.
try:
    desiredSum = int(sys.argv[1])
except:
    desiredSum = 22

# Init sevens to get at or beyond sum, fours to zero, and the sum.
(numSevens, numFours) = ((desiredSum + 6) // 7, 0)
thisSum = numSevens * 7 + numFours * 4

# Continue until a solution is found.
while thisSum != desiredSum:
    if thisSum > desiredSum:
        # Too high, remove a seven. If that's not possible, exit.
        if numSevens == 0:
            print(f"{desiredSum}: no solution")
            sys.exit(0)
        numSevens -= 1
        thisSum -= 7
    else:
        # Too low, add a four.
        numFours += 1
        thisSum += 4

# Only get here if solution found, so print lowest
# possible number that matches four/seven count.
print(f"{desiredSum}: answer is {'4' * numFours}{'7' * numSevens}")

And here's a transcript of it in action for a small sample range:

pax:~> for i in {11..20} ; do ./test47.py ${i} ; done
11: answer is 47
12: answer is 444
13: no solution
14: answer is 77
15: answer is 447
16: answer is 4444
17: no solution
18: answer is 477
19: answer is 4447
20: answer is 44444

And here's the (rough) digit count for a desired sum of four billion, well over half a billion digits:

pax:~> export LC_NUMERIC=en_US.UTF8
pax:~> printf "%'.f\n" $(./test47.py 4000000000 | wc -c)
571,428,597

---

If you really need a C++ solution, see below. I wouldn't advise using this if this is course-work, instead suggesting you convert the algorithm shown above into your own code (for reasons previously mentioned). This is provided just to show the similar approach in C++:

#include <iostream>

int main(int argc, char *argv[]) {
    // Get desired sum from command line, defaulting to 22.
    int desiredSum = 22;
    if (argc >= 2) desiredSum = atoi(argv[1]);

    // Init sevens to get at or beyond desired sum, fours to zero,
    // and the sum based on that.
    int numSevens = (desiredSum + 6) / 7, numFours = 0;
    int thisSum = numSevens * 7 + numFours * 4;

    // Continue until a solution is found.
    while (thisSum != desiredSum) {
        if (thisSum > desiredSum) {
            // Too high, remove a seven if possible, exit if not.
            if (numSevens == 0) {
                std::cout << desiredSum << ": no solution\n";
                return 0;
            }
            --numSevens; thisSum -= 7;
        } else {
            // Too low, add a four.
            ++numFours; thisSum += 4;
        }
    }

    // Only get here if solution found, so print lowest
    // possible number that matches four / seven count.
    std::cout << desiredSum << ": answer is ";
    while (numFours-- > 0)  std::cout << 4;
    while (numSevens-- > 0)  std::cout << 7;
    std::cout << '\n';
}

---

Of course, you can be even more clever when you realise that the maximum number of fours will be six, and that you can add one to the sum-of-digits by removing one seven and adding two fours.

So simply:

• work out the number of sevens required to get at or just below the desired sum;
• add a single four if that will still keep you at or below the desired sum;
• then adjust by enough actions of "remove one seven and add two fours" until you get to that desired sum (keeping in mind you may already be there). This will be done exactly once for each unit the shortfall in your current sum (how far it is below the desired sum) so, if the shortfall was two, you would remove two sevens and add four fours (- 14 + 16 = 2). That means you can use a simple mathematical formula rather than a loop.
• if that formula results in a negative count of sevens, there was no solution, otherwise use the counts as previously mentioned to form the lowest number (fours followed by sevens).

Just Python for this solution, given how easy it is:

import sys

# Get desired number.
desiredNum = int(sys.argv[1])

# Work out seven and four counts as per description in text.

numSevens = int(desiredNum / 7)          # Now within six of desired sum.
shortFall = desiredNum - (numSevens * 7)
numFours = int(shortFall / 4)            # Now within three of desired sum.
shortFall = shortFall - numFours * 4

# Do enough '+7-4-4's to reach desired sum (none if already there).
numSevens = numSevens - shortFall
numFours = numFours + shortFall * 2

# Done, output solution, if any.
if numSevens < 0:
    print(f"{desiredNum}: No solution")
else:
    print(f"{desiredNum}: {'4' * numFours}{'7' * numSevens}")

That way, no loop is required at all. It's all mathematical reasoning.

Answer 2

The constraints for sum are 1 ≤ n ≤ 10⁶

It means that you might have to find and print numbers with more than 10⁵ digits (10⁶ / 7 ≅ 142,857). You can't store those in a fixed-sized integral type like long long, it's better to directly generate them as std::strings composed by only 4 and 7 characters.

Some mathematical properties may help in finding a suitable algorithm.

• We know that n = i * 4 + j * 7.

• Of all the possible numbers generated by each combination of i digits four and j digits seven, the minimum is the one with all the fours at left of all the sevens. E.g. 44777 < 47477 < 47747 < ... < 77744.

• The minimal lucky number has at max six 4 digits, because, even if the sum of their digits is equal, 4444444 > 7777.

Now, let's introduce s = n / 7 (integer division) and r = n % 7 (the remainder).

• If n is divisible by 7 (or when r == 0), the lucky number is composed only by exactly s digits (all 7).

• If the remainder is not zero, we need to introduce some 4. Note that

  • If r == 4, we can just put a single 4 at the left of s sevens
  • Every time we substitute (if we can) a single 7 with two 4s, the sum of the digits increases by 1.
  • We can calculate exactly how many 4 digits we need (6 at max) without a loop.

This is enough to write an algorithm.

#include <string>

struct lucky_t
{
    long fours, sevens;
};

// Find the minimum lucky number (composed by only 4 and 7 digits)
// that has the sum of digits equal to n.
// Returns it as a string, if exists, otherwise return "-1".
std::string minimum_lucky(long n)
{
    auto const digits = [multiples = n / 7L, remainder = n % 7L] {
        return remainder > 3
            ? lucky_t{remainder * 2 - 7, multiples - remainder + 4}
            : lucky_t{remainder * 2, multiples - remainder};
    } ();

    if ( digits.fours < 0  ||  digits.sevens < 0 )
    {
        return "-1";
    }
    else
    {
        std::string result(digits.fours, '4');
        result.append(digits.sevens, '7');
        return result;
    }
}

Tested here.

Answer 3

If I understand the question correctly, you are searching for the smallest number x which contains only the numbers 4 and 7 and the sum of its digits N. The smallest number is for sure written as:

 4...47...7

and consists of m times 4 and n times 7. So we know that N = n · 4 + m · 7.

Here are a couple of rules that apply:

1. (n + m) · 7 ≥ N :: This is evident, just replace all 4's by 7's.
2. (n + m) · 4 ≤ N :: This is evident, just replace all 7's by 4's.
3. (n + m) · 7 − N = m · (7 − 4) :: in other words (m+n) · 7 − N needs to be divisible by 7 − 4

So with these two conditions, we can now write the pseudo-code very quickly:

# always assume integer division
j = N/7                       # j resembles n+m (total digits)
if (N*7 < N) j++              # ensure rule 1
while (  (j*4 <= N) AND ((j*7 - N)%(7-4) != 0) ) j++  # ensure rule 2 and rule 3
m = (j*7 - N)/(7-4) # integer division
n = j-m
if (m>=0 AND n>=0 AND N==m*4 + n*7) result found

Here is a quick bash-awk implementation:

$ for N in {1..30}; do 
    awk -v N=$N '
        BEGIN{ j=int(N/7) + (N%7>0);
               while( j*4<=N && (j*7-N)%3) j++;
               m=int((j*7-N)/3); n=j-m;
               s="no solution";
               if (m>=0 && n>=0 && m*4+n*7==N) {
                   s=""; for(i=1;i<=j;++i) s=s sprintf("%d",(i<=m?4:7))
               }
               print N,s
        }'
 done
1 no solution
2 no solution
3 no solution
4 4
5 no solution
6 no solution
7 7
8 44
9 no solution
10 no solution
11 47
12 444
13 no solution
14 77
15 447
16 4444
17 no solution
18 477
19 4447
20 44444
21 777
22 4477
23 44447
24 444444
25 4777
26 44477
27 444447
28 7777
29 44777
30 444477