e189: 3的倍數 - 面試題

2019-09-04

內容

3 的倍數？沒有錯~又是 3 的倍數！

大家都知道判斷 3 的倍數就是把每一位相加，如果是 3 的倍數就能被 3 整除

那你知道如何不用除法” / “，取餘數” % “來判斷是否為 3 的倍數嗎？

輸入

每一行有一個數字 n，0 <= n <= 2147483647

EOF 結束

1
2
3

輸出

輸出該數字是否為三的倍數

如果是，輸出”YES”

否則，輸出”NO”

NO
NO
YES

解題思路

當一數的二進制偶數位和奇數位相差為 3 的倍數，則該數為 3 的倍數。

完整程式碼

AC (2ms, 96KB)

#include <stdio.h>

char mult3(int src)
{
    int res = 0;
    do
    {
        res += src & 1;
        src >>= 1;
        res -= src & 1;
    } while (src >>= 1);
    if (res < 0)
        res = -res;
    return res == 0 || res == 3 || res == 9 || res == 12 || res == 15 ||
        res == 18 || res == 21 || res == 24 || res == 27 || res == 30;
}

int main()
{
    int n;
    while (scanf(" %d", &n) == 1)
    {
        puts(mult3(n) ? "YES" : "NO");
    }
    return 0;
}