Counter Game program in Hacker Rank

Question

I have solved the problem of HackerRank with c#. But while submitting the code Test cases from 9 gets terminated due to timeout error.

Louise and Richard have developed a numbers game. They pick a number and check to see if it is a power of 2. If it is, they divide it by 2. If not, they reduce it by the next lower number which is a power of 2. Whoever reduces the number to 1 wins the game. Louise always starts.

Given an initial value, determine who wins the game.

Example

It's Louise's turn first. She determines that 132 is not a power of 2. The next lower power of 2 is 128, so she subtracts that from 132 and passes 4 to Richard. 4 is a power of 2, so Richard divides it by 2 and passes 2 to Louise. Likewise, 2 is a power so she divides it by 2 and reaches 1. She wins the game.

Update If they initially set counter to 1, Richard wins. Louise cannot make a move so she loses.

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'counterGame' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts LONG_INTEGER n as parameter.
     */

    public static string counterGame(long n)
    {
        // Write your code here
        int isWho = 0;
        
        while(n != 1)
        {
            int pow=0;
            long n_maximus = n;
            
            while(n_maximus > 1)
            {
                n_maximus >>= 1; 
                pow++; 
            }

            long minPow = 1 << pow; 
            if(n - minPow == 0)
            {
                n = n >> 1; 
            }
            else 
            {
                n -= minPow; 
            }
            
            isWho++; /
            
        }
        
        return (isWho & 1) != 0 ? "Louise" : "Richard";
    }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int t = Convert.ToInt32(Console.ReadLine().Trim());

        for (int tItr = 0; tItr < t; tItr++)
        {
            long n = Convert.ToInt64(Console.ReadLine().Trim());

            string result = Result.counterGame(n);

            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
}

If the code is working but slow, it's probably better suited to [Code Review](https://codereview.stackexchange.com/). Please ensure that it is working and slow, and not simply buggy though, as Code Review does require that code is working. — ProgrammingLlama, Mar 16 '22 at 09:47
Hint, try using `long.MaxValue / 2` and see how long it takes to compute, then look at what is consuming all that time and try to come up with a better approach. — Lasse V. Karlsen, Mar 16 '22 at 09:50
You could use bitwise "tricks" to optimize your solution. Number `x` is a power of two if `x & (x - 1) == 0`. Subtracting by the next lower number which is a power of 2 is nothing more then setting the leftmost bit to 0, which you could do [this way](https://stackoverflow.com/a/27742068/4778343). — Stefan Golubović, Mar 16 '22 at 10:43

score 1 · Answer 1 · answered Mar 16 '22 at 13:06

The reason for timeout is long minPow = 1 << pow;. If you debug your code with some large value, you'll see that minPow is not even close the value you would expect.

For example, try your code with 660570904136157. pow will be 49, and 1 << pow will be 131072, but you would expect 562949953421312.

The reason for that is because 1 is an int, and not long. What you actually get is 1 << 17, i.e. 1 << (49 - 32). To get correct result you should specify that 1 is a long with 1L. Your code will pass all tests when you change long minPow = 1 << pow; with long minPow = 1L << pow;.

Counter Game program in Hacker Rank

1 Answers1