Artur Sokhikyan
BAN USERThis answer is almost correct.
Some corrections: "which color occurs even number of times"
this is not correct since there are 100 prisoners and the number of hats are both even or both odd.
Actually first prisoner should count the one color (say it is agreed to be RED) and should say RED if the reds are even or Black if the reds are odd.
This is the best algo imho. I did this with exactly the same code. and it is definitly O(n).
- Artur Sokhikyan March 29, 2012private static void IsDivisibleBy3()
{
int counter = 0;
bool evenOddFlag = true;
while (true)
{
var nextBit = Console.ReadKey().KeyChar;
if(nextBit == 'x')
break;
if (nextBit == '1')
{
counter += evenOddFlag ? 1 : -1;
}
evenOddFlag = !evenOddFlag;
if(nextBit == '0' || nextBit == '1')
Console.WriteLine(counter % 3 == 0 ? "\tDivisible" : "\tNot divisible");
else
Console.WriteLine("\tIncorrect bit value");
}
}
here is the proof.
Our goal is to show that every 2^k number could be represented as 3*p +/- 1 (plus or minus) form, and also if 2^k = 3p + 1 then 2^(k+1) = 3*q - 1 and vice versa.
first part is very easy. every integer can be represented in one of the following 3 forms: 3*p - 1 (or the same is 3*q + 2), 3*p or 3*p + 1. Note that 2^k <> 3*p as 2^k does not contain 3 multiplier, so 2^k = 3*p - 1 or 2^k = 3*p + 1.
now assume 2^k = 3*p - 1. Then 2^(k+1) = 2 * (3*p - 1) = 6*p - 2 = 3 * (2*p) - 2 = 3 * q + 1. And the same we can do for 2^k = 3*p+1.
private static void RearrangeLinkedList(LinkedList head, uint skip /* M */, uint delete /* N */)
{
if(head == null || skip < 1 || delete < 1)
return;
bool flag = skip != 1; // skip if true
uint counter = skip == 1 ? delete : skip - 1;
LinkedList node = head;
while (node.Next != null)
{
if (flag)
node = node.Next;
else
node.Next = node.Next.Next;
if(--counter == 0)
{
counter = flag ? delete : skip;
flag = !flag;
}
}
}
O(2n) no additional buffer (only output array)
- Artur Sokhikyan August 30, 2013