Check if a given number is sum of 3s, 5s, and 7s with efficient approach in C++

Given a non negative number, you are required to find whether or not the number can be composed from sum of some number of 7s, 5s and 3s i.e. if a number is of the format n=3x+5y+7z (x, y, z being non negative integers), if not print -1. If it is of the required format, print the number of 3s, 5s and 7s that need to be added to obtain the given number.

Examples:

Input: 3
Output: 1 0 0
Explanation: 3*1+5*0+7*0=3, thus one 3, no 5 and no 7 are needed.
Input: 4
Output: -1
Explanation: 5>4, 7>4 and 3<4. Thus 3+ (5 or 7) will be greater than 4 too so no combination of 3s, 5s and 7s can be used for representing 4.

Naive Approach:

Run 3 loops for finding the combination of x, y, z satisfying the equation 3x+5y+7z=n.

The worst case is one where the number can’t be split into required combination since the we would have to try all possible combinations for the code to conclude none of them fits the equation.

Below is the implementation of the above approach:

#include <iostream>
using namespace std;

int main()
{

    // flag indicates when the required combination is
    // found
    int n = 10, flag = 0;
    // loop varying value of number of 3s
    for (int i = 0; i <= n / 3; i++) {
        if (flag == 1)
            break;

        // loop varying value of number of 5s
        for (int j = 0; j <= n / 5; j++) {
            if (flag == 1)
                break;
            // loop varying value of number of 7s
            for (int k = 0; k <= n / 7; k++) {
                if (3 * i + 5 * j + 7 * k == n) {
                    flag = 1;
                    cout << i << " " << j << " " << k;
                    break;
                }
            }
        }
    }

    // if no combination has been found print -1
    if (flag == 0)
        cout << -1;

    return 0;
}

Output:

0 2 0

Time Complexity: O(n^3)
Auxiliary Space: O(1)
The time complexity can be reduced to constant using a more efficient approach.

Efficient Approach:

We will never need 5 and 7 together to represent a number as 5+7 can be represented as 3*4, thus a number that can be represented by some 5s and 7s can also be represented by some number of 3s and 5, or some number of 3s and 7. There are 3 possibilities whereby n can be composed of 3s, 5s and 7s:

Number completely divisible by 3 – If so, the number can be composed of n/3 number of 3s, zero 5s and zero 7s.
Number leaving remainder 1 with 3 – When the number leaves remainder of 1 on division with 3, we can split the number into 3s and 7s. As n-1 is divisible by 3, n-1-6 will also be divisible by 3. As the remainder was 1, and we subtracted 6 from n-1, on adding this 6 to remainder we obtain 7. The number is thus split into (n-7)/3 number of 3s, one 7 and zero 5s. If on subtracting 6 from n-1 it became negative then the number was less than 7, thus can’t be split into 7 and 3s.
Number leaving remainder 2 with 3 – When the number leaves remainder of 2 on division with 3, we can split the number into 3s and 5s. As n-2 is divisible by 3, n-2-3 will also be divisible by 3. As the remainder was 2, and we subtracted 3 from n-2, on adding this 3 to remainder we obtain 5. The number is thus split into (n-5)/3 number of 3s, one 5 and zero 7s. If on subtracting 3 from n-2 it became negative then the number was less than 5, thus can’t be split into 5 and 3s.

If none of the above constitutions were possible then the number can’t be represented as a sum of 3s, 5s and 7s.

Below is the implementation of the above approach:

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

int main()
{
    // f indicates possibility of splitting the number into
    // 3, 5, 7 only, when f=0 then number can't be formed by
    // only combination of a number of 3s, 5s and 7s
    int n = 10, f = 0;

    // if n is completely divisible by 3 it can be composed
    // of all 3s
    if (n % 3 == 0) {
        cout << n / 3 << " " << 0 << " " << 0 << endl;
        f = 1;
    }
    else if (n % 3 == 1) {

        // if the number on division with 3 leaves a
        // remainder of 1, 1+6 and n-1-6 can be 2 parts of
        // the number, composed of 7 and 3s
        if (n - 7 >= 0) {
            cout << (n - 7) / 3 << " " << 0 << " " << 1
                 << endl;
            f = 1;
        }
        else
            f = 0;
        // if the number is less than 7, splitting it into a
        // 7 and 3s won't be possible
    }
    else {

        // when remainder is 2, 3+2 and n-3-2 could be the
        // composition of the number
        if (n - 5 >= 0) {
            cout << (n - 5) / 3 << " " << 1 << " " << 0
                 << endl;
            f = 1;
        }
        else
            f = 0;
        // if n is less than 5, splitting into a 5 and
        // 3s won't be possible
    }

    // when all possibilities are exhausted and f is still 0
    // we output -1
    if (f == 0)
        cout << -1 << endl;
}

Output:

1 0 1

Time Complexity: O(1)
Auxiliary Space: O(1)