<p>Your algorithm is correct and its running time is in $\Theta(n)$ which is exponential to the input size. But we can use simple greedy algorithm to achive $O(\log n)$. Find largest number $i$ such that $i! \le n$. To do so just simply iterate through numbers in $1,\cdots, \log n +1$. And do the same for $n -i!$.</p>

CC BY-SA 3.0
2014-12-26T05:31:46.150Z
+1; you (qiubit) should convince yourself that the greedy algorithm _does_ work (in the sense that it provides the minimum $k$), of course, but that's not too difficult a thing to do here.
Steven Stadnicki
CC BY-SA 3.0
2014-12-26T00:53:45.377Z
2014-12-28T09:34:49.060Z
2014-12-28T09:34:49.060Z
Saeed
<p>Here is a problem I'm trying to solve:</p>

<p>Given an integer $n$ return a list $[x_1,x_2,...,x_k]$ such that $n=x_1!+x_2!+...+x_k!$ and $k$ is as low as it can be.</p>

<p>I'm thinking of creating a list of n ones, then pairing them as long as I can (so for example $[1,1,1,1,1]$ becomes $[2,2,1]$) then I want to exchange all triples of $[2,2,2]$ to one $3$ (because $2!+2!+2!=3!$) and so on...</p>

<p>Intuitively this should be correct, and also quite fast - the input on which I'm executing my "concatenations" shrinks as fast as factorial function grows...</p>

<p>But is my method correct? And also if I were to find complexity of my algorithm in terms of $n$, how should I do that? One more thing, maybe there is simpler way to solve this algorithmic problem - any ideas?</p>

<ds.algorithms><time-complexity>
Finding $x_1,x_2,...,x_k$ such that $n=x_1!+x_2!+...+x_k!$ and $k$ is minimal
qiubit
# Finding $x_1,x_2,...,x_k$ such that $n=x_1!+x_2!+...+x_k!$ and $k$ is minimal

(Asked by: username_0 on 2014-12-25)

Here is a problem I'm trying to solve:

Given an integer $n$ return a list $[x\_1,x\_2,...,x\_k]$ such that $n=x\_1!+x\_2!+...+x\_k!$ and $k$ is as low as it can be.

I'm thinking of creating a list of n ones, then pairing them as long as I can (so for example $[1,1,1,1,1]$ becomes $[2,2,1]$) then I want to exchange all triples of $[2,2,2]$ to one $3$ (because $2!+2!+2!=3!$) and so on...

Intuitively this should be correct, and also quite fast - the input on which I'm executing my "concatenations" shrinks as fast as factorial function grows...

But is my method correct? And also if I were to find complexity of my algorithm in terms of $n$, how should I do that? One more thing, maybe there is simpler way to solve this algorithmic problem - any ideas?

**Tags:** ds.algorithms, time-complexity


---

## 1 answers

### Answer by username_1 on 2014-12-26. Score: 9 | Accepted answer

Your algorithm is correct and its running time is in $\Theta(n)$ which is exponential to the input size. But we can use simple greedy algorithm to achive $O(\log n)$. Find largest number $i$ such that $i! \le n$. To do so just simply iterate through numbers in $1,\cdots, \log n +1$. And do the same for $n -i!$.

> **Comments:**
> **username_2**: +1; you (username_0) should convince yourself that the greedy algorithm _does_ work (in the sense that it provides the minimum $k$), of course, but that's not too difficult a thing to do here.  

---

