[面試] 3 的倍數 @ Edison.X. Blog

很莫名的， 3 的倍數面試問題筆者看過兩次，限制有點不同，仔細想想後，拿來當面試題目一點都不過份。

Q1. 如何「只用加減乘除法」判斷整數是否為 3 的倍數？

Q2. 如何「不用除法與取模」判斷整數是否為 3 的倍數？

Q1 是某碩士班面試題目，Q2 是某科技業面試題目。

為了簡化說明，我們先把範圍調到「正整數 x」，這假設也不過份，只是單純的 if-else 取絕對值，如果要用 bitwise hacker 取絕對值也無妨。

int input;
int x1 = (input >= 0) ? input : -input; // better
int x2 = (unsigned)input & ~( 1U<< (sizeof(input)*CHAR_BIT));

減法判斷

一種較低效但通用的方法是，進行連減判斷。

while(x>2) x-=3;
if(x==0) puts("yes");
else puts("no");

可推到判斷 n 之倍數。無庸致疑，非常低效。

乘法判斷

在可以進行乘法之情況下很容易，只要除 3 再乘 3 判斷就行。

if(x/3*3==x) puts("yes");
else puts("no");

可推到判斷 n 之倍數。

不用除法與取模

Q2 題意敘述有些爭議，有些網友認為，left shift operator 與 and operator 本身便是一種除法與取模之運算，如果這二個 operator 也被禁用的話，那就慢慢從減法判斷吧。

這裡假設可用 shift operator 與 and operator。

看到這題目 5 分鐘後 (很可惜，若是面試的話面試官不會等我 5 分鐘 )，想到以 binary 方式思考。

97 mod 3 = (64+32 + 1) mod 3 = 1 mod 3 = 1

一個莫名不知定理的東西推出來了： 2ⁿ + 2⁽ⁿ⁺¹⁾ 必為 3 之倍數

鑑於此思考模式之範例碼如下。

unsigned Mod3(unsigned x)
{
        unsigned sum;
        do{
                sum = 0;
                while(x) {
                        sum+=x&0x3; // 取最後 2 bits
                        x>>=2;
                }
                x = sum;
        }while(sum>3);
        return sum==3 ? 0 : sum; // 最後等於 3 額外判斷
}

很遺憾的，這方式雖比累減高，但效率比起其他方式，算很低。

另 3(dec) = 11 (bin)，轉個念頭思考，判斷 10 進位之 3 ，和判斷 2 進位之 11 頗為相似，而題意只是要判斷「是否」為3之倍數，而不是真的要求「mod 3 之結果」，可以拿來做應用。

#include <stdio.h>
unsigned IsMulti3(unsigned x)
{
    unsigned i, remain=x;
    unsigned c0, c1;
    do{        
        c0 = c1 = 0U;
        // 偶位數 1 個數 : c0
        for(i=remain; i; i>>=2) c0+=(i&1U);
        // 奇位數 1 個數 : c1
        for(i=remain>>1; i; i>>=2) c1+=(i&1U);
        // c0-c1
        remain = (c0>=c1) ? c0-c1 : c1-c0;
    }while(remain > 3);
    return (remain==3 || remain==0);
}
int main()
{
    unsigned x=0;
    while(scanf("%u", &x)==1)
        printf("%u%u\n", IsMulti3(x), (x%3==0));
    return 0;
}