The problem statement as follows :
I have total N coins & I have to make K piles . I have to distribute the coins into the piles so that each piles contain >=1 coins .
Output a permutation of K number (Which denotes the number of coins in each piles ) that the first player to move lose in **Normal Nim Game**
More specefic : two condition :
1. n1 + n2 + n3 +... ... + nk = N
2. n1 ^ n2 ^ n3 ^ ... ... ^nk = 0
Here n <= 10^8 , k <=N Time : 3s
An O(k + logN) solution:
1) Set to 1 the first bit in
numbers. If 
then set to 1 the second bit of the last 2 numbers. Subtract all considered bits from n.
2) Now we do not need to care about the condition ni > 0 anymore. Pick the biggest
and set to 1 (z - 1)-th bits of the first 2 numbers. If thay are already set then assign them 0 and try to put 1 on z-th bit and so on. Subtract 2z from n and repeat.
For some n there will be no solution.
The only problem will be with k = 3, z ≤ 1.
I believe you are able to deal with this case :)
bitwise xor of k bits will be zero if there is even number of 1 .. That's the first observation I have made .. But how this will all sum up to N ?
I don't understand .. PavelSavchenkov Can you explain more . please ?
Actually, in the second step we decompose n to the binary notation,
.
Special for you.
My different approach: Let's decompose n to his binary notation b1b2... We take every bit of n — adding ith bit as two i - 1th bits to next two nl numbers. For example N = 23, we add 8 to 1th and 2nd number, we add 4 to 3rd and 4th number and so on (modk).
It can happen that we used all k number and our job is done.
But if we didn't?
We have to make "push" operations:
Let's take ai and ai + 1 — the two smallest used numbers. They have j-th bit turned on. We move this bit one forward (»1) and add 2j - 1 to ai + 2 and ai + 3 (sum stays the same and xor = 0). We keep doing these until we can or we used k numbers. If we didn't, there is no solution.
Complexity: O(k + logn) — at most k / 2 push operations.