2 Keys Keyboard


  • 0

    Click here to see the full article post


  • 0
    N

    Well, the following argument excerpted from this article is not strong enough. How can you make sure a split in three parts "pqk" is no better than spliting in two parts "pq"?

    "Such a split never uses more moves: we use p+q moves when splitting, and pq moves previously. As p+q <= pq is equivalent to 1 <= (p-1)(q-1), which is true as long as p >= 2 and q >= 2."


  • 0

    @newtt If any g_i are composite, we showed that there exists a split such that it uses less moves. This proves that any optimal solution cannot have g_i composite. Any factorization g = p * q (regardless of whether p, q are prime, just as long as they are at least 2) is sufficient.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.