Question

We are given a bit sequence in the form of 64-bit integer. We pass through the bits from left to right and we flip all sequences of 3 equal bits (111 -> 000, 000 -> 111). For example, 8773276988229695713 represents the bit sequence 0111100111000000111100001111000000011111100010100011100011100001. We flip from left to right all 3 consecutive equal bits: 0111100111000000111100001111000000011111100010100011100011100001 ->  0000100000111111000111100001111111000000011110111100011100011101.

The obtained 64-bit number after flipping is 594226797558351645.

Your task is to write a program that enters a 64-bit integer, performs the above described flipping, and prints the obtained result as a 64-bit integer.

Input

The input data should be read from the console. It consists of a single 64-bit integer number.

The input data will always be valid and in the format described. There is no need to check it explicitly.

Output

Print at the console the 64-bit integer, representing the obtained bits after the flipping.

Constraints

• The input number will be a 64-bit integer in the range [0 … 18 446 744 073 709 551 615].
• Allowed working time for your program: 0.1 seconds.
• Allowed memory: 16 MB.

Examples

Answer 1

Here's my solution:

using System;

class BitFlipper
{
    static void Main()
    {

        ulong num = ulong.Parse(Console.ReadLine());

        string numAsString = Convert.ToString((long)num, 2).PadLeft(64, '0');//WE MAKE THE NUMBER STRING -> SO WE CAN READ IT FROM LEFT TO RIGHT

        char[] array = numAsString.ToCharArray();//CONVERT THE STRING TO CHAR ARRAY TO CHANGE THE ELEMENTS AFTERWARDS -> WE CANNOT CHANGE STRINGS ELEMENTS

        for (int i = 2; i < array.Length; i++)
        {
            if (array[i] == array[i - 1] && array[i - 1] == array[i - 2])
            {
                if (array[i] == '0')
                {
                    array[i] = '1';
                    array[i - 1] = '1';
                    array[i - 2] = '1';
                }
                else
                {
                    array[i] = '0';
                    array[i - 1] = '0';
                    array[i - 2] = '0';
                }
                i += 2;
            }
        }
        //Console.WriteLine(array);//TO CHECK AS A BIT IN THE CHAR ARRAY
        Console.WriteLine(Convert.ToUInt64(new string(array), 2));
    }
}

 

Answer 2

Here's another solution with bits - not with strings/chars:

using System;
using System.Runtime.InteropServices;

class BitFlipper
{
    static void Main()
    {

        ulong num = ulong.Parse(Console.ReadLine());

        for (int i = 61; i >=0; i--)
        {
            ulong threeeBits = (num >> i) & 7;//USING 7 BECAUSE IT IS 111
            if (threeeBits == 0 || threeeBits == 7)
            {
                num = num ^ (ulong)7 << i;
                i -= 2;
            }
        }
        Console.WriteLine(num);
    }
}