প্রাচীন অ্যালগরিদমিক ম্যাজিকের একটি বিট, বা লিটকোড থেকে কাজগুলির একটি আকর্ষণীয় ক্রম সমাধান করা

কিছু সময় আগে, আমি ওয়েবসাইট leetcode.com-এ কাজগুলির একটি মজাদার সিরিজ দেখেছিলাম। কাজগুলি নিজেরাই খুব কঠিন নয়, তবে তাদের সমাধানগুলি বেশ আকর্ষণীয়। তদুপরি, এই ধরণের সমস্যাগুলি প্রায়শই বড় সংস্থাগুলিতে সাক্ষাত্কারে উপস্থিত হয় এবং তাদের সমাধানের পদ্ধতিগুলি বোঝা বেশ উপকারী হতে পারে।

প্রথম কাজ হল 136. একক সংখ্যা (সহজ)

পূর্ণসংখ্যার একটি অ-খালি অ্যারে দেওয়া যেখানে একটি ছাড়া প্রতিটি উপাদান দুবার প্রদর্শিত হয়, আপনাকে একটি জোড়া ছাড়াই উপাদানটি খুঁজে বের করতে হবে। O(n) সময়ের জটিলতায় এবং ধ্রুবক অতিরিক্ত মেমরির সাথে সমস্যার সমাধান করুন।

উদাহরণ 1:

ইনপুট: সংখ্যা = [1, 3, 3, 2, 6, 2, 1]

আউটপুট: 6

উদাহরণ 2:

ইনপুট: সংখ্যা = [12, 1, 1, 7, 1, 12, 1]

আউটপুট: 7

উদাহরণ 3:

ইনপুট: সংখ্যা = [6]

আউটপুট: 6

আমরা XOR ফাংশন প্রপার্টি লিভারেজ করব, যেটির অপারেন্ড ভিন্ন হলেই 1 পাওয়া যায়। অ্যারের সমস্ত উপাদানের মধ্য দিয়ে অতিক্রম করে এবং সেগুলিতে বিটওয়াইজ XOR সম্পাদন করে, আমরা সমস্ত অভিন্ন বিট মানকে শূন্য করে দেব। ফলস্বরূপ, যা অবশিষ্ট থাকে তা হবে কাঙ্ক্ষিত ফলাফল।

এখানে একটি ছোট Python3 সমাধান কোড আছে:

 def single_number(nums: list) -> int: result = 0 for el in nums: result ^= el return result

আমরা একটি পূর্ণসংখ্যা দখল করে যতটা অতিরিক্ত মেমরি ব্যবহার করি, এবং প্রদত্ত অ্যারের মাধ্যমে একটি একক পাসে সমাধান খুঁজে বের করি, আমাদের O(n) জটিলতা দেয়। এটি একটি সংক্ষিপ্ত এবং মার্জিত সমাধান।

দ্বিতীয় সমস্যা হল 137. একক সংখ্যা II (মাঝারি অসুবিধা)

পূর্ণসংখ্যার একটি অ-খালি অ্যারে দেওয়া যেখানে প্রতিটি উপাদান একটি ছাড়া তিনবার প্রদর্শিত হয়, এবং শুধুমাত্র একটি উপাদান একবার উপস্থিত হয়, আমাদের এই অনন্য উপাদানটি খুঁজে বের করতে হবে। O(n) সময়ের জটিলতায় এবং ধ্রুবক অতিরিক্ত মেমরির সাথে সমস্যার সমাধান করুন।

উদাহরণ 1:

ইনপুট: সংখ্যা = [৩, ১, ৩, ৩]

আউটপুট: 1

উদাহরণ 2:

ইনপুট: সংখ্যা = [12, 1, 1, 5, 1, 12, 12]

আউটপুট: 5

উদাহরণ 3:

ইনপুট: সংখ্যা = [6]

আউটপুট: 6

দুর্ভাগ্যবশত, আমরা এই ক্ষেত্রে পূর্ববর্তী কৌশলটি ব্যবহার করতে পারি না যেহেতু আমরা প্রয়োজনীয় অবস্থানে জোড়া বিটগুলিকে শূন্যে পরিণত করতে পারি না। পূর্ববর্তী টাস্ক থেকে প্রদত্ত অ্যারেটিকে বিন্যাসে রূপান্তর করা এবং তারপর একইভাবে এটি সমাধান করা প্রলুব্ধ হবে।

এইভাবে যুক্তি দিয়ে, এটা লক্ষ্য করা সহজ যে যদি আমরা জানতাম যে অ্যারেটি অতিক্রম করার সময় আমরা ইতিমধ্যেই N সংখ্যার মুখোমুখি হয়েছি দুইবার (বা তিনবার) তবে আমরা যে যোগফলটি পাচ্ছি তার সাথে N এর সাথে একটি অতিরিক্ত XOR যোগ করতে পারি। এটি এই সংখ্যার সাথে চূড়ান্ত XOR কে সমান করবে, যার ফলে এটিকে চূড়ান্ত যোগফল থেকে সরিয়ে দেওয়া হবে, এবং যা অবশিষ্ট থাকবে তা হবে আমাদের উত্তর।

 def single_number_ii(nums: list) -> int: mem = {} result = 0 for el in nums: if not mem.get(el, False): mem[el] = 1 else: mem[el] += 1 if mem[el] == 2: result ^= el result ^= el return result

দুর্ভাগ্যবশত, এই সমাধানটির জন্য মেমরির পরিপ্রেক্ষিতে সর্বাধিক (len(nums)-1)/3 প্রয়োজন, যা ধ্রুবক ব্যবহার হিসাবে বিবেচিত হতে পারে না, তাই আমাদের অন্য সমাধান খুঁজতে হবে।

আসুন আমাদের পদ্ধতি পরিবর্তন করার চেষ্টা করুন।

এর আগে, আমরা XOR ব্যবহার করতাম (যা যোগ মডিউল 2 প্রতিনিধিত্ব করে)। আমরা যদি সংযোজন মডুলো 3 প্রয়োগ করতাম, আমরা আগের উদাহরণ থেকে সহজে কৌশলটি প্রয়োগ করতে পারতাম।

আমরা যদি প্রথমবার মুখোমুখি হই উত্তরে একটি সংখ্যা লিখতে পারি, দ্বিতীয়বার এটিকে সঞ্চয়কারীতে রাখতে পারি এবং তৃতীয়বার উত্তর এবং সঞ্চয়কারী উভয়কেই শূন্য করতে পারি, তাহলে এটি আমাদের একটি পাস-থ্রুতে সমস্যা সমাধান করতে সহায়তা করবে। দুটি পূর্ণসংখ্যার সমান অতিরিক্ত মেমরি খরচ সহ তালিকা, টাস্ক প্রয়োজনীয়তা পূরণ করে।

সুতরাং, আসুন আরও বিটওয়াইজ ম্যাজিক প্রয়োগ করি:

 def single_number_137_ii(nums: list) -> int: ans, acc = 0, 0 for n in nums: ans = ans ^ n & ~acc acc = acc ^ n & ~ans return ans

এইভাবে, সমস্ত ট্রিপল সংখ্যা শূন্য হয়ে যায়, এবং আমাদের কাছে শুধুমাত্র সেই সংখ্যাটি অবশিষ্ট থাকে যা শুধুমাত্র একবার ঘটে।

তৃতীয় কাজ হল 260। একক সংখ্যা III (মাঝারি অসুবিধা)

পূর্ণসংখ্যার একটি অ-খালি অ্যারে দেওয়া যেখানে প্রতিটি উপাদান দুবার প্রদর্শিত হয়, শুধুমাত্র একবার প্রদর্শিত দুটি উপাদান ছাড়া, আমাদের এই অনন্য উপাদানগুলি খুঁজে বের করতে হবে। লক্ষ্য হল O(n) সময়ের জটিলতায় এবং ধ্রুবক অতিরিক্ত মেমরির সাথে সমস্যার সমাধান করা, এবং অনন্য উপাদানের ক্রম কোন ব্যাপার নয়।

উদাহরণ 1:

ইনপুট: সংখ্যা = [1, 2, 1, 3, 2, 5]

আউটপুট: [3, 5]

উদাহরণ 2:

ইনপুট: সংখ্যা = [1, -2]

আউটপুট: [-2, 1]

স্পষ্টতই, আমরা XOR অপারেশন ব্যবহার করে সহজেই সমস্ত জোড়া সংখ্যা মুছে ফেলতে পারি, যেমন আমরা প্রথম কাজটি সমাধান করেছিলাম। কাজটির জটিলতা তখন যেকোন একটি অনন্য সংখ্যা চিহ্নিত করার মধ্যে নিহিত থাকে, যার পরে দ্বিতীয়টি সহজেই আমাদের XOR যোগফলের সাথে XOR-ing করে গণনা করা যায়।

এটি অর্জন করার জন্য, আমাদের কেবল এই অনন্য সংখ্যাগুলির মধ্যে কোনও পার্থক্য খুঁজে বের করতে হবে। তারপর, আমরা আবার অ্যারের মাধ্যমে পুনরাবৃত্তি করি, XOR সমষ্টি সম্পাদন করি এবং ফলাফলগুলিকে দুটি গ্রুপে ভাগ করি - সংখ্যাগুলির জন্য যেখানে এই বিটটি সেট করা হয়েছে এবং যেখানে এটি 0। ফলস্বরূপ, আমরা পছন্দসই অনন্য উপাদানগুলি পাই।

 def single_number_260(nums: list) -> int: res1, res2 = 0, 0 glob_xor = 0 for n in nums: glob_xor ^= n diff_bit = glob_xor & ~(glob_xor - 1) for n in nums: if n & diff_bit: res1 ^= n else: res2 ^= n return [res1, res2]

অ্যারের মাধ্যমে দুবার পুনরাবৃত্তি করা সত্ত্বেও, জটিলতা O(n) থেকে যায় এবং মেমরি খরচ মাত্র 2 পূর্ণসংখ্যা।

দ্রষ্টব্য: পাইথনে int অন্যান্য ভাষার int-এর মতো না হওয়া সত্ত্বেও, আমরা এর আকারকে ধ্রুবক হিসাবে বিবেচনা করব