We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Counter game
  2. Discussions

Counter game

Sort by

recency

|

199 Discussions

|

  • IvanDominis
     + 0 comments
    Basic Javascript Solution
    1. Find the next lower power of 2 less than N using while loop
    2. Compare with N to adjust N value and move to next turn
    3. Loop step 1, 2 until N is 1 and return the winner.
    function counterGame(n){
	const player = ['Louise', 'Richard'];
	let count = 0;
	while ( n > 1 ){
		let p = 0;
		while ( 2**p < n){
			p++;
		}
		if ( 2**p === n ) n/=2;
		else n -=2**(p-1);
		count++;
	}
	return player[(count+1)%2];
}

  • dotaikhoa
     + 0 comments

    c++ solution i prepare an array that stores consecutive values of power of 2. then i do simulation of the game and checking if the current 'n' is power of 2 which in binary has only 1 bit set, hence i use built-in function to count bits that are 1 in a number. I also keep track of who would win at the moment in 'louise' variable

    string counterGame(long n) {
    const int l = 63;
    vector<long> pows(l);
    for (long i = 0; i < l; i++) {
        pows[i] = (1l<<i);
    }
    
    bool louise = false;
    
    while (n > 1) {
        louise ^= 1;
        
        auto lb = lower_bound(pows.begin(),pows.end(),n);
        int indx = distance(pows.begin(), lb);
        
        if (__builtin_popcount(n)==1) {
            n >>= 1l;
        } else {
            n -= pows[indx-1];
        }
    }
    
    return louise ? "Louise" : "Richard";
}

  • hank_ring
     + 0 comments
    def counterGame(n):
    return 'Richard' if (n.bit_count() + bin(n)[::-1].index('1')) & 1 else 'Louise'

  • darren80
     + 0 comments

    Javascript (ugly, non-math-based version)

    function counterGame(n: number): string {
  const powersOfTwo = [1];
  let player = 'Richard';
  
  while (n !== 1) {
    player = player === 'Louise' ? 'Richard' : 'Louise';
    
    while (powersOfTwo[powersOfTwo.length-1] < n) {
      powersOfTwo.push(powersOfTwo[powersOfTwo.length-1] * 2);
    }
    
    if (powersOfTwo.includes(n)) {
      n /= 2;
    } else if (n !== 1) {
      let nextLowestPowOfTwo;
      for (let i=0; i < powersOfTwo.length; i++) {
        if (powersOfTwo[i] > n) {
          nextLowestPowOfTwo = powersOfTwo[i-1];
          break;
        }
      }
      n -= nextLowestPowOfTwo
    }
  }
  
  return player;
}

  • e0425559
     + 1 comment

    C# O(1) one-liner:

    public static string counterGame(long n)
{
    return (long.PopCount(n) + long.TrailingZeroCount(n)) % 2 == 0 ? "Louise" : "Richard";
}

    Makes use of POPCNT and TZCNT instructions, both O(1) on x86.