ধরা যাক একটি অ্যারে আছে যেখানে 1 থেকে N পর্যন্ত প্রতিটি সংখ্যা একবার করে থাকতে পারে, কিন্তু অ্যারের আকার (N-4) অর্থাৎ চারটি সংখ্যা অনুপস্থিত। আমাদের সেটি চারটি অনুপস্থিত সংখ্যা সর্টেড أور্ডারে বের করতে হবে।
ইনপুট: A=[2,8,4,13,6,11,9,5,10] → আউটপুট [1,3,7,12]।
সমাধানের ধাপসমূহ (অ্যারে ইনডেক্স ব্যবহার করে মার্কিং)
- temp_arr[4] = 0 দিয়ে ইনিশিয়ালাইজ
- for i in 0..len(A)-1:
- temp = abs(A[i])
- যদি temp <= len(A): A[temp-1] *= -1 (নেগেটিভ করে মার্ক)
- অন্যথায় (temp > len(A)):
- যদি temp % len(A) != 0: temp_arr[temp%len(A)-1] = -1
- অন্যথায়: temp_arr[(temp%len(A))+len(A)-1] = -1
- for i in 0..len(A)-1: যদি A[i] > 0: print i+1
- for i in 0..3: যদি temp_arr[i] >= 0: print len(A)+i+1
উদাহরণ
def find_missing_nums(A):
temp_arr = [0]*4
for i in range(len(A)):
temp = abs(A[i])
if temp <= len(A):
A[temp - 1] = A[temp - 1] * (-1)
elif temp > len(A):
if temp % len(A):
temp_arr[temp % len(A) - 1] = -1
else:
temp_arr[(temp % len(A)) + len(A) - 1] = -1
for i in range(len(A)):
if A[i] > 0:
print(i + 1, end=" ")
for i in range(len(temp_arr)):
if temp_arr[i] >= 0:
print(len(A) + i + 1, end=" ")
A = [2, 8, 4, 13, 6, 11, 9, 5, 10]
find_missing_nums(A)
ইনপুট
[2, 8, 4, 13, 6, 11, 9, 5, 10]
আউটপুট
1 3 7 12
