不吉利的數字

不吉利的數字（不HOMEWORK）不吉利的數字

有被認爲是不吉利的幾號（它僅包含4和7）。我們的目標是在正整數a和b的範圍內找到這樣的數字。
例如：
輸入：A = 10 B = 20
輸出：0
輸入：A = 30 B = 50
輸出：2（44，47）

下面是我試圖代碼使用靜態數組方法，其中我最初計算一個32位整數的所有可能的不幸的數字。這在O（n）中完成，然後順序掃描有助於獲得再次是O（n）操作的計數。如果沒有靜態數組的幫助，有沒有更好的方法來解決這個問題？

#define MAX_UNLUCKY 1022 
static int unlucky[MAX_UNLUCKY]; 
int main(int argc, char **argv) { 
    int i, j, k; 
    int a, b, factor; 
    printf("Enter the numbers : \n"); 
    scanf("%d",&a); 
    scanf("%d",&b); 
    unlucky[0] = 4; 
    unlucky[1] = 7; 
    factor = 10; 
    k = 1; 
    for(i = 2; i < MAX_UNLUCKY; ++i) 
     unlucky[i] = unlucky[(i >> 1) - 1]*factor + unlucky[k ^= 1]; 
    for (i = 0; i < MAX_UNLUCKY;++i) 
     if (unlucky[i] > a) break; 
    for (k = i; k < MAX_UNLUCKY;++k) { 
     if (unlucky[k] > b) break; 
     printf("Unlukcy numbers = %d\n", unlucky[k]); 
    } 
    printf ("Total Number of Unlucky numbers in this range is %d\n", k-i); 
    return (0); 
}

來源

2011-09-18 Anoop Menon

優化小記：你的方法'K = 1;'[.. 。]'+ unlucky [k^= 1];'生成序列'4,7,4,7,4 ...'使用一個數組查找，你可以使用類似'k = 7;'[ ...] +（k = 11-k）'。 – schnaader

正在做作業嗎？ –

我很確定它可能在'log（n）^ k'時空中（小常數k，但我懶得計算實際的k）。你只需要計算計數，你不需要枚舉全部。你可以使用數字10^n以下的2^n個不幸的數字。 – CodesInChaos

考慮以下幾點：

多少數字是有

之間

0x100 and 0x111? 

100,101,110,111 (4 = 0x111 - 0x100 + 1)

那到底有多少不吉利的數字也有744和777（744747774777）之間。

現在：

700和800具有相同的它們之間不吉利的數字爲744和777 744比700和777更大的最小不吉利的數字比800

較小的最大不吉利的數字

不需要生成數字，只需減去。

對於像A = 10，B = 800的情況下，先找到你的電話號碼爲10-100，然後100-800（因爲你會被計算兩次一些數字）：

10-100：

a = 44 
b = 77 

0x11 - 0x00 = 3 + 1 = 4 (44,47,74,77)

對於100-800：數字4 + 8 = 12，這也是正確的：

a = 444 
b = 777 

0x111 - 0x000 = 7 + 1 = 8 (444, 447, 474, 477, 744, 747, 774, 777)

所以10和800之間。

這也是O（1）時間，如果你有效地找到輔助號碼&空間，這應該不是太難......

來源

2011-09-18 09:58:49

如果你正在分裂它的數字，那麼你不會得到O（ 1），因爲你將做Θ（log（n））計算。這就是說，我可以想出兩個簡單的技巧來解決這個問題。 – Nabb

請分享:)。另外，爲簡單起見，我們假設數量有限。我的意思是，如果你想完全理論化，那麼加法是O（n） - 因爲你必須逐個數字地加上：P –

雖然你不得不承認...... :) –

不吉利的數字

回答

相關問題