Counter game

HackerRank 問題: Counter game

Question

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 wins the game. Louise always starts.

Given an initial value, determine who wins the game.

HackerRank 問題: Counter game

說明

條件

  1. 當數字是 2 的指數倍數,則將數字除以 2
  2. 當數字不是 2 的指數倍數,與小於數字,且最接近的指數倍數的,當作是下一個數字
目前數字 下個數字 說明
64 32 是 2 的指數倍數,執行條件 1,(64/2)=32
92 28 不是 2 的指數倍數,執行條件 2,92 以下的 2 的指數數字是 64,(92-64)= 28

2 的指數表

2 指數倍數 結果
0 1
1 2
2 4
3 8
4 16
5 32
6 64
7 128
8 256
9 512
10 1024

解決問題

  1. 找出是 2 的指數計算次數
  2. 找出非 2 的指數計算次數

2 的指數計算

下表為列出 2 的指數的二元表,可以看到當數字為 2 的指數時,除了最前方為 1,後面則都為 0

當遇到 條件 1當數字是 2 的指數倍數,則將數字除以 2

所以後面的運算都是除以 2,剛好後面 0 的出現次數,就是要除以 2 的運算次數

數字 - 256 128 64 32 16 8 4 2 1 - 除 2 除到 1 運算次數(0 的出現次數)
256 - 1 0 0 0 0 0 0 0 0 - 8
128 - 0 1 0 0 0 0 0 0 0 - 7
64 - 0 0 1 0 0 0 0 0 0 - 6
32 - 0 0 0 1 0 0 0 0 0 - 5
16 - 0 0 0 0 1 0 0 0 0 - 4
8 - 0 0 0 0 0 1 0 0 0 - 3
4 - 0 0 0 0 0 0 1 0 0 - 2
2 - 0 0 0 0 0 0 0 1 0 - 1
1 - 0 0 0 0 0 0 0 0 1 - 0

非 2 的指數計算

以數字 496 為例,可以看到他的二進位數字是 11110000,以下是所有執行步驟

步驟 數字 - 256 128 64 32 16 8 4 2 1 下個數字 誰執行動作
1 496 - 1 1 1 1 1 0 0 0 0 496 - 256 = 240 Louise
2 240 - 0 1 1 1 1 0 0 0 0 240 - 128 = 112 Richard
3 112 - 0 0 1 1 1 0 0 0 0 112 - 64 = 48 Louise
4 48 - 0 0 0 1 1 0 0 0 0 48 - 32 = 16 Richard
5 16 - 0 0 0 0 1 0 0 0 0 16 / 2 = 8 Louise
6 8 - 0 0 0 0 0 1 0 0 0 8 / 2 = 4 Richard
7 4 - 0 0 0 0 0 0 1 0 0 4 / 2 = 2 Louise
8 2 - 0 0 0 0 0 0 0 1 0 2 / 2 = 1 Richard
9 1 - 0 0 0 0 0 0 0 0 1 不能除了,輸了 Louise

在步驟 1 ~ 4 時,因為後面的二進位皆有 1 出現,所以一定非 2 可以整除的數字(非 2 的指數),所以遇到 條件2與小於數字,且最接近的指數倍數的,當作是下一個數字

1 ~ 4 步驟可以剛好看到,那個差值剛好是將二進位數字,最前面的 1 拿掉變為 0,就是這個差值,所以等於是在遇到 2 的指數數字前,1 的數量有多少個,就是使用 條件2 運算的次數

在步驟 5 ~9 時,可以看到數字變為 2 的倍數了,所以會用條件 1當數字是 2 的指數倍數,則將數字除以 2,最後會算出來,輸的是 Louise,贏的是 Richard

計算邏輯拆分 2 種,2 的指數與非 2 的指數

剛剛在上方有提到,當遇到 2 的指數數字,運算的次數就是 後方 0 的數字多寡,所以等於是使用 條件 1 執行的次數

所以 16(10000),後面 0 的數字有 4 個,所以 條件 1 要運算 4 次

步驟 數字 - 16 8 4 2 1 下個數字
5 16 - 1 0 0 0 0 16 / 2 = 8
6 8 - 0 1 0 0 0 8 / 2 = 4
7 4 - 0 0 1 0 0 4 / 2 = 2
8 2 - 0 0 0 1 0 2 / 2 = 1
9 1 - 0 0 0 0 1 不能除了,輸了

當遇到非 2 的指數,使用 條件 2 執行的次數為遇到 2 的指數 1,前面 1 的數量,就是執行的次數

最後會遇到 2 的指數數字為 16,所以在 16(10000) 之前 1 出現的次數,496(111110000) 1 出現的次數是 4 次(排除 16 本身的 1),所以 條件 2 要運算 4 次

步驟 數字 - 256 128 64 32 16 8 4 2 1 下個數字
1 496 - 1 1 1 1 1 0 0 0 0 496 - 256 = 240
2 240 - 0 1 1 1 1 0 0 0 0 240 - 128 = 112
3 112 - 0 0 1 1 1 0 0 0 0 112 - 64 = 48
4 48 - 0 0 0 1 1 0 0 0 0 48 - 32 = 16
5 16 - 0 0 0 0 1 0 0 0 0 16 / 2 = 8

統整運算邏輯

條件 1 是 0 出現的次數,條件 2 是 1 出現的次數,為了方便計算,直接將整個數字 -1,就會從 496(111110000) 變成 495(111101111)

步驟 數字 - 256 128 64 32 16 8 4 2 1
1 496 - 1 1 1 1 1 0 0 0 0
1 496 - 1 1 1 1 0 1 1 1 1

這樣等於 條件 1 是 0 出現的次數就變成 1 出現的次數,那接下來只需要計算所有 1 出現的次數,就可以知道整個遊戲玩了幾輪,就可以知道誰輸誰贏了

條件 程式 結果
遊玩次數為 偶數(even) play_game_times % 2 = 0 Richard 贏
遊玩次數為 奇數(odd) play_game_times % 2 = 1 Louise 贏

Answer

Python

def counterGame(n)
  setbits = bin(n-1).count('1')

  if setbits%2 == 0:
    return 'Richard'
  else:
    return 'Louise'

PHP

<?php

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

function counterGame($initial_number)
{
    // calculate bit 1 number for play game times
    $play_game_times = 0;

    $initial_number -= 1;
    while($initial_number) {
        // if the number is exponent 2(last 1 occur), then the result will be 0, and end the while loop
        $initial_number = $initial_number & ($initial_number -1);
        $play_game_times++;
    }

    // calculate play game times to find winner
    if ($play_game_times % 2 == 0) {
        $winner = 'Richard';
    } else {
        $winner = 'Louise';
    }

    return $winner;
}

$fptr = fopen(getenv("OUTPUT_PATH"), "w");

$t = intval(trim(fgets(STDIN)));

for ($t_itr = 0; $t_itr < $t; $t_itr++) {
    $n = intval(trim(fgets(STDIN)));

    $result = counterGame($n);

    fwrite($fptr, $result . "\n");
}

fclose($fptr);

C

int setBits(unsigned long long int n) {
    int count = 0 ;
    while(n) {
    	n &= (n-1) ;
        count ++ ;
    }
    return count ;
}

int main() {
    int t ;
    scanf("%d\n",&t) ;
    while(t--) {
        unsigned long long int n ;
        scanf("%llu\n",&n) ;
        if (setBits(n-1) & 1) printf("Louise\n") ;
        else printf("Richard\n") ;
    }
    return 0;
}

Reference