Verilen bir tamsayı dizisinde, her elemanın yalnızca bir kez göründüğü ve 1'den n'e kadar olan tüm sayıların bulunduğu bir diziden eksik olan sayıyı bulun. Dizideki sayılar 1 ile n arasında olup, n dizinin uzunluğudur.
Örnek:
Kod:
Girdi: nums = [4,3,2,7,8,2,3,1]
Çıktı: 5Kısıtlamalar:
- Dizinin uzunluğu n'dir.
- 1 ≤ nums[i] ≤ n
- Her sayı yalnızca bir kez görünür, ancak bir sayı eksik.
Bu problemi çözmek için XOR işlemini kullanabiliriz. XOR'un özellikleri sayesinde, aynı sayılar birbirini sıfırlarken eksik olan sayı bulunabilir. Algoritma şu şekilde çalışır:
- 1'den n'e kadar olan tüm sayıların XOR'unu hesapla.
- Dizideki tüm sayıların XOR'unu hesapla.
- Bu iki XOR sonucunu birbiriyle XOR yaparak eksik sayıyı bul.
Kod:
def findMissingNumber(nums):
n = len(nums)
xor_all = 0
for i in range(1, n + 1):
xor_all ^= i
xor_array = 0
for num in nums:
xor_array ^= num
return xor_all ^ xor_array
# Test
nums = [4, 3, 2, 7, 8, 2, 3, 1]
print(findMissingNumber(nums)) # Çıktı: 5- Adım 1: xor_all, 1'den n'e kadar olan sayıların XOR'unu tutar. Örneğin, n=8 için 1^2^3^4^5^6^7^8 hesaplanır.
- Adım 2: xor_array, dizideki tüm sayıların XOR'unu tutar. Örneğin, [4,3,2,7,8,2,3,1] için 4^3^2^7^8^2^3^1 hesaplanır.
- Adım 3: xor_all ^ xor_array işlemi, aynı sayıların birbirini sıfırlaması nedeniyle yalnızca eksik sayıyı döndürür.
- Zaman Karmaşıklığı: O(n), çünkü diziyi ve 1'den n'e kadar olan sayıları birer kez tarıyoruz.
- Uzay Karmaşıklığı: O(1), çünkü yalnızca birkaç değişken kullanıyoruz.