CODEWITHSUNDEEP
c++algorithm
Katreque
Katreque

Reputation: 338

Sum of factoriais to be equal a given number

I'm trying to solve the following problem:

What is the smallest number of factoriais summed that are needed to be equal an given number a? (1 ≤ a ≤ 10^5)

Example:

Input: 10, Output: 3. (10 = 3! + 2! + 2!)

Input: 25, Output: 2. (25 = 4! + 1!)

My code:

#include<bits/stdc++.h>

using namespace std;

int a;

int rec(int vet){
    
    int count = 0;
    
    a = a - vet;
        if(a >= vet){
            count++;
            rec(vet);
        }
    count++;
    return count;
}

int main(){
    
    int vet[8] = {1}, count = 0;
    
    cin >> a;
    
    for(int i = 2; i <= 8; i++){
        vet[i-1] = vet[i-2]*i;
    }
    
    for(int i = 7; i >= 0; i--){
        if(a < vet[i]){
            continue;
        }
        
        count += rec(vet[i]);
    }
    
    cout << count << endl;
}

My logic:

1°: a max is equal to 100000, so the maximum fatorial we have to compare is 8!;

2°: I take a factioral that is equal or nearest small to a, subtract the factorial from it and count++; If after the subtraction, a still bigger then my factorial, I do the same step recursively.

This code pass on the base cases, but I got a wrong answer. I wasn't capable to find what case it didn't pass, so I'm here.

Can you find where am I wrong? Or if my solution is not good and I should try another approach.

Thanks for the help!

Upvotes: 1

Views: 106

Answers (2)

Ep1c
Ep1c

Reputation: 21

The problem is easily solved by a recursive approach.

Here is checked code:

    #include <iostream>

using namespace std;

int factorial(int n) {
        return n<=1 ? 1 : n * factorial(n-1);
    }


int MinFact(int number)
{
            static int num_of_facts;
            int a = 1;
            if (number)
            {
                        while(factorial(a+1)<=number)a++;
                        cout << a << "!" << endl;
                        num_of_facts++;
                        MinFact((number-factorial(a)));
            }
            return num_of_facts;
}


int main()
{
            int num;
            cout << "Enter number" << endl;
            cin >> num;
            num = MinFact(num);
            cout << "Number of factorials: " << num;
            return 0;
}

Upvotes: 1

Ajay Brahmakshatriya
Ajay Brahmakshatriya

Reputation: 9203

As I mentioned in the comment, the issue is with the rec function. Due to rec being local, the count is not being incremented correctly.

A simple solution would be to replace the rec function as follows

int rec(int vec) {
    int count = a / vec;
    a = a % vec;
    return count;
}

Edit : for a failing case try 18. The solution will be 3 but you will get 2. I guess you can figure out how this logic works. If not you could do it with a loop.

Upvotes: 0

Related Questions