LeetCode - Single Number
Problem Description here
Problem: এই প্রব্লেমে আমাদেরকে একটি ইন্টিজার অ্যারে দেয়া থাকবে যেখানে একটি সংখ্যা বাদে বাকি সংখ্যাগুলো এক্সেক্টলি দুইবার করে থাকবে এবং ঐ সংখ্যাটি একবার থাকবে।
আমাদেরকে একবার থাকা সংখ্যাটি বের করতে হবে। O(n) Time Complexity এবং O(1) Memory Complexity তে কাজটি করতে হবে।
Solution: বিটওয়াইজ অপারেশনগুলো নিয়ে মোটামুটি ধারণা আছে এমন যেকেউ প্রথম দেখায় প্রব্লেমটি সলভ করতে পারবে। আমরা জানি,
1 XOR 1 = 0
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
বিটওয়াইজ এক্সর এর ফর্মুলা গুলো জানা থাকলে দেখবে যে একই সংখ্যা দুইবার এক্সর করলে ফলাফল শূন্য!
আসলে, দুইবার নয়। যেকোন জোড় সংখ্যকবার একটি সংখ্যাকে এক্সর করলে ফলাফল শূন্য।
যেহেতু, অ্যারে তে ১টি সংখ্যা বাদে বাকিসব সংখ্যা ই দুইবার করে আছে সেহেতু অ্যারের সবগুলো সংখ্যা এক্সর করলে যে সংখ্যাটি পাওয়া যায় সেটিই আমাদের কাঙ্ক্ষিত সংখ্যা।
Comments
Post a Comment