Split N into maximum composite numbers

Reading time: 30 minutes | Coding time: 5 minutes

Given a number N, the problem is to count the maximum number of composite numbers that sum up to N. First few composite numbers are 4, 6, 8, 9, 10, 12, 14, 15...

A composite number is an integer other than 1 and prime numbers. Prime Numbers are integers which is divisible by only two numbers that is 1 and the number itself.

Print -1 if the number cannot split into composite number (eg: 5, 7, 11)

Example

1. N = 15 => 6 + 9

15 can be split into 6 + 9, so the output of 15 will be 2.

2. N = 30 => 4 + 4 + 4 + 4 + 4 + 4 + 6

30 can be split into many different ways like 10 + 10 + 10, but to maximize the count of composite number we split the 30 in 6 composite numbers.

Greedy Approch

So to maximize the number of composite number we have to increase the count small number which sum up to the given number.Since smallest composite number is 4, it makes sense to use maximum number of 4s

Takking a greedy approch we try divide the given number by 4, for numbers that don’t leave a composite remainder when divided by 4, we do following:

• If remainder is 1, we subtract 9 from it to get the number which is perfectly divisible by 4.
• If the remainder is 2, then subtract 6 from it to make n a number which is perfectly divisible by 4.
• If the remainder is 3, then subtract 15 from it to make n perfectly divisible by 4, and 15 can be made up by 9 + 6.

Explanation

Let us take N = 90

90 is not completely divided by 4, so we calculate its reminder i.e; 2.
According to the algoritms we subtract 6 from N => 90-6 = 84.

We divide 84 with 4 which gives us 21, which means we can split 84 into 21 4's and for the remaining value we can add 6 (another composite number) which will sum up the number to 6 => 84 + 6 = 90.

So 90 can be spit into 21 4's and one 6 which sum up to 21 composite number.

Code

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

// function to calculate the maximum number of
// composite numbers adding upto n
int countCompositeNumber(int n)
{
    // 4 is the smallest composite number
    // if any number is smaller than 4 cannot be spllited further
    if (n < 4)
        return -1;

    // stores the remainder when n is divided
    // by 4
    int rem = n % 4;

    // if remainder is 0, then it is perfectly
    // divisible by 4.
    if (rem == 0)
        return n / 4;

    // Case1:   if the remainder is 1
    if (rem == 1)
    {

        // If the number is less then 9, that
        // is 5, then it cannot be expressed as
        // 4 is the only composite number less
        // than 5
        if (n < 9)
            return -1;

        // If the number is greater then 8, and
        // has a remainder of 1, then express n
        // as n-9 a and it is perfectly divisible
        // by 4 and for 9, count 1.
        return (n - 9) / 4 + 1;
    }

    // Case 2: When remainder is 2
    // Just subtract 6 from N,
    // so that N is perfectly divisible by 4 and
    // count 1 for 6 which is subtracted.
    if (rem == 2)
        return (n - 6) / 4 + 1;

    // Case 3:When rem is 3

    if (rem == 3)
    {
        // if the number is 7, 11 which cannot be
        // expressed as sum of any composite numbers
        if (n < 15)
            return -1;

        // when the remainder is 3, then subtract
        // 15 from it and n becomes perfectly
        // divisible by 4 and we add 2 for 9 and 6,
        // which is getting subtracted to make n
        // perfectly divisible by 4.
        return (n - 15) / 4 + 2;
    }
}

int main()
{
    int N = 90;
    cout << N << " can be splited into maxmimum of " <<  countCompositeNumber(N) << " Composite numbers" << endl;

    N = 143;
    cout << N << " can be splited into maxmimum of " <<  countCompositeNumber(N) << " Composite numbers" << endl;
    return 0;
}

Output:

90 can be splited into maxmimum of 22 Composite numbers
143 can be splited into maxmimum of 34 Composite numbers

Complexity

• Worst case time complexity: Θ(1)
• Space complexity: Θ(1)

Assuming that division operation takes constant time O(1). In reality, division operation takes logarithmic time O(log N) but the system does several optimizations over this which makes the real time performance significantly good.

In reality, the time complexity is O(log N).

Complexity