İçeriğe geç

Yarıya indir ya da bir çıkar

Kolay#tail-recursion#bit-counting~15 dk

Görev tanımı

Problem

Sıfır ya da daha büyük bir n tam sayısından başla. Bir adımda çiftse onu yarıya indir, tekse bir çıkar. Sıfıra ulaşmanın kaç adım sürdüğünü döndür. Sayı 2 üzeri 1000 kadar büyük olabilir, bu yüzden adım başına bir özyinelemeli çağrı yapan bir çözüm Python'un varsayılan özyineleme (recursion) sınırını aşar.

Örnekler

Input:  n = 14
Output: 6
Neden: 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0
Input:  n = 2 ** 1000
Output: 1001
Neden: 1000 yarıya indirme 1'e, bir çıkarma da 0'a ulaşır
Input:  n = 0
Output: 0
Neden: edge case: zaten sıfırda, yani hiç adım atılmaz

İpuçları

0 / 3

Hedef zaman
O(log n)
Hedef alan
O(1)

Kısıtlar

  • 0 ≤ n ≤ 2¹⁰⁰⁰

Kodda değil de fikirde mi takıldın? Tail call'lar ve döngüler bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case