IQ Test

Posted on | In

題目

Bob is preparing to pass IQ test. The most frequent task in this test is to find out which one of the given numbers differs from the others. Bob observed that one number usually differs from the others in evenness. Help Bob — to check his answers, he needs a program that among the given numbers finds one that is different in evenness, and return a position of this number.

Keep in mind that your task is to help Bob solve a real IQ test, which means indexes of the elements start from 1 (not 0) (Link)

思路

傳入的numbers是只用空格分開的連續字串，我想先把他們分開並只把數字的部份加入到新的list內，例如 “2 4 6 8 10” → [2, 4, 6, 8, 10]。接著依序檢查list內的各項是屬於odd或even，若與其他人不同則挑出，並回傳他在list中的位置。

Pseudocode

1
2
3
4
5
6
7
8
9
10
arr = []
for i in 傳入的字串
  如果是空格
    跳過
  如果不是
    加到arr內

for i in arr
  如果此項與前後項是不同性質的
    回傳此項目的位置

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def iq_test(numbers):
    arr = []
    ele = ''
    for i in numbers:
        if i == ' ':
            arr.append(int(ele))
            ele = ''
            continue
        else:
            ele += i
    arr.append(int(ele))

    for j in range(len(arr)-1):
        if (arr[j-1]%2==0) != (arr[j]%2==0) != (arr[j+1]%2==0):
            return j+1
    return len(arr)               # Runtime: 144 ms

分析

第一個段落中，由於字串會被一個個字元檢視，若傳入的其中一個數字是兩位數(如10)，就可能被拆成’1’和’0’分別加入到arr內。所以在這裡使用ele來暫時儲存字元，只要還沒遇到空格，就會與下一個字元做字串的相加。

第二個段落中，若目標項目在最後一項，可能會因為arr[j+1]而產生Index error，所以我只讓迴圈執行range(len(arr)-1)次，若迴圈結束還是沒找到目標，那麼就回傳最後一項。

此演算法的運作時間：

  • 兩次for-loop皆為O(n)
  • arr.append為O(1)

整體Time complexity 為 O(n)

參考他人作法

1
2
3
def iq_test(numbers):
    e = [int(i) % 2 == 0 for i in numbers.split()]
    return e.index(True) + 1 if e.count(True) == 1 else e.index(False) + 1           # Runtime: 141 ms

分析

我的code的第一段在做的事情與str.split()類似。此方法的功能如下：

str.split(sep=None, maxsplit=-1)

  • sep表示分割字元，預設為None，凡是’’, ‘ ‘, /n等代表None的都符合
  • maxsplit表示分割次數，預設為-1，所以若沒有設定，就會一直分到字串結束為止

接著以%2 == 0的條件來讓各個數字變為True或False，計算只有一個True或只有一個False的那一方，那就是目標了。