Lucky numbers 4s and 7s

[Kalcor]

Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya wonders eagerly what minimum lucky number has the sum of digits equal to n. Help him cope with the task.

Input
The single line contains an integer n (1 ≤ n ≤ 106) — the sum of digits of the required lucky number.

Output
Print on the single line the result — the minimum lucky number, whose sum of digits equals n. If such number does not exist, print -1.

Examples
input
11
output
47
input
10
output
-1

I, after alot of tries have failed to solve this problem and looked for a solution till I found this:

#include <iostream>
#include <stdio.h>
using namespace std;

int main(){

bool flag = false;
 int n;
 cin>>n;
 if(n<4){
 cout<<"-1";
 return 0;
 }
 for (int i = n / 7; i>= 0; i --) {
 int j = n - (i * 7);
 if (j% 4 == 0) {
 flag = true;
 for (int P = 0; P <j / 4; P ++) cout<<4;
 for (int Q = 0; Q <i; Q ++) cout<<7<<endl;
 break;

}

}
 if(!flag) cout<<-1<<endl;

}

I don't understand the concept behind this loop and why were these values like n/7 or j%4 or n - (i*7) were used

 //lines 14 to 24 above.
for (int i = n / 7; i>= 0; i --) {
 int j = n - (i * 7);
 if (j% 4 == 0) {
 flag = true;
 for (int P = 0; P <j / 4; P ++) cout<<4;
 for (int Q = 0; Q <i; Q ++) cout<<7<<endl;
 break;

}

}

Would like your ideas / solutions ^^

[doug4]

Here's what the code is doing.

First of all, the smallest number that adds up to a target will have as few digits as possible. This means the number will have as many 7's as possible rather than 4's. For instance, summing up to 28 with 7's will yield 7777, but using 4's would be 4444444, significantly larger than the number with all 7's. So, get as many 7's into the mix as possible, reducing the number of required digits.

The for loop in line 2

for (int i = n / 7; i>= 0; i --) {

loops from the maximum number of 7's (n / 7) to 0 7's. By checking the largest number of 7's first, the first solution that we find will have the fewest possible number of digits, leading, eventually, to the smallest number.

The next line int j = n - (1 * 7); gets the remainder of the original number after subtracting out the number of 7's that are being test in the current loop iteration. So, for the number 15, if we are trying 2 7's, the remainder after removing the 7's is "1". Likewise, if we are trying 1 "7", the remainder after removing the 7's is "8".

After determining the remainder, we check to see if it is a multiple of 4. If so, we can insert some number of 4's into the number to generate the remainder. That's why the algorithm checks if (j % 4 == 0).

At this point, if the remainder is a multiple of 4, we know that number can be generated using some fixed (but as of yet unknown) number of 4's and a known number of 7's. Given the set of all possible numbers with some fixed count of 4's and another fixed count of 7's, the smallest number in the set will be the one that has all of the 4's before all of the 7's. (e.g. 447 < 474 < 744). So, we print our the all of the 4's first and then all of the 7's. That gives you the smallest number made up of 4's and 7's whose sum of the digits adds up to the target value.