حل مسئله «اعداد یکتا» کوئرا با سی‌شارپ

بسم الله الرحمن الرحیم

به امید خدا توی این مطلب می‌خوایم مسئله «اعداد یکتا» که در سایت Quera هست رو حل کنیم.

حل این مسائل، علاوه براینکه باحاله و سرگرمی :) تمرینی هستن برای افزایش مهارت حل مسئله ما.

برای دیدن مجموعه سوالاتی که از سایت کوئرا حل کردم می‌تونید این مخزن رو ببینید.

مسئله: اعداد یکتا

صورت مسئله کامل رو می‌تونید در سایت کوئرا ببینید. به صورت خلاصه:

یک دنباله از اعداد بهمون میدن. اول باید اعداد یکتا (اعدادی که فقط یکبار در دنباله هستن) رو پیدا کنیم. بعد عملیات XOR روی اون‌ها انجام بدیم و در آخر، خروجی رو چاپ کنیم.

راه‌حل با زبان سی‌شارپ

می‌تونید کد کامل رو از این لینک ببینید.

اگر نمی‌دونید عملیات ریاضی XOR چی هستش، سایت کوئرا توضیح مختصر و خوبی ارائه داده:

منظور از XOR (مخفف eXclusive OR) دو عدد صحیح و نامنفی مثل a و b که آن را به صورت a⊕b نیز نشان می‌دهند، این است که اگر دو عدد a و b را در مبنای دو زیرهم بنویسیم. (اگر یکی از این اعداد تعداد رقم کمتری دارد پشت آن صفر در نظر بگیرید.) سپس برای هر دو رقم زیرهم اگر یکسان باشند رقم متناظر حاصل، صفر و در غیر این صورت یک خواهد بود.
برای مثال برای محاسبه 12⊕6 ابتدا این دو عدد را در مبنای دو می‌نویسیم (باید پشت ۶ صفر اضافه کنیم تا تعداد ارقام برابر شود.) سپس به صورت رقم به رقم نگاه می‌کنیم و اگر ارقام متناظر در این دو عدد برابر بودند، ۰ و در غیر این‌صورت ۱ می‌گذاریم یعنی:

همچنین از تعریف مشخص است که این عمل، خاصیت «جابه‌جایی» و «شرکت‌پذیری» دارد. یعنی اگر m عدد داشته باشیم، ترتیب این اعداد و یا ترتیب عملیات‌ها بر روی حاصل نهایی تاثیری ندارد. بنابراین پاسخ مسئله فقط یک حالت دارد.

برای اینکه توضیحات طولانی نشه و با توجه به اینکه گرفتن ورودی‌ها نکته خاصی نداره، صرفا به متد اصلی که باید پیاده‌سازی بشه می‌پردازم. امضای متد اصلی ما به این صورت هستش:

void PrintXorUniqueNumbers(IEnumerable<int> numbers) {

} 

متد ما قراره لیستی از اعداد صحیح بگیره و در نهایت، خروجی رو چاپ کنه.

در قدم اول باید اعداد یکتا رو پیدا کنیم.

برای اینکار می‌تونیم از متد GroupBy استفاده کنیم. این متد میاد دنباله ما رو گروه‌بندی می‌کنه. مثلا فرض کنید لیستی از دانشجوها بهتون دادن و ازتون خواستن اون‌ها رو براساس رشته مرتب کنید. خروجی کار شما چطوری میشه؟

• رشته مکانیک: لیست افراد
• رشته عمران: لیست افراد

متد GroupBy هم همینکار رو میکنه. توی ورودی ازتون میپرسه مجموعه رو بر چه اساسی مرتب کنم؟ ما می‌گیم براساس خود اعداد:

var uniqueNumbers = numbers.GroupBy(number => number)

مثلا اگر دنباله ما به صورت 4 3 2 7 8 2 3 1 باشه، خروجی کد بالا به صورت زیر خواهد بود:

همونطور که در تصویر مشخصه، اعداد گروه‌بندی شدن:

• عدد ۴: لیست عددهای ۴
• عدد ۲: لیست عددهای ۲
• و ...

اینطوری می‌تونیم بفهمیم هر عدد چندبار تکرار شده. حالا باید بگیم از این لیست، اون‌هایی رو انتخاب کن که یکتا هستن:

var uniqueNumbers = numbers.GroupBy(number => number)
    .Where(group => group.Count() == 1)

بعدش برای اینکه لیست اعداد رو داشته باشیم فقط فیلد Key رو انتخاب می‌کنیم.

var uniqueNumbers = numbers.GroupBy(number => number)
    .Where(group => group.Count() == 1)
    .Select(group => group.Key)
    .ToList();

خب حالا برسیم به عملیات اصلی. ما یه لیست از اعداد داریم که باید عملیات XOR رو روی اون‌ها انجام بدیم. باید عدد اول رو با عدد دوم XOR کنیم، بعد خروجی رو با عدد سوم XOR کنیم و الی آخر. متد Aggregate دقیقا همینکار رو برای ما انجام میده.

var xor = uniqueNumbers.Aggregate((result, nextNumber) => nextNumber ^ result);

توی سی‌شارپ، برای عملیات xor از ^ استفاده می‌کنیم.

عملیات بالا یه عدد از لیست uniqueNumbers میگیره، بعد با result (که مقدار پیشفرض int یعنی صفر هستش) xor میکنه و در result قرار میده. بعد دوباره یه عدد از uniqueNumbers می‌گیره و الی آخر.

قسمت پایانی: در آخر مسئله گفته شده اگر هیچ عدد یکتایی نبود، عدد ۰ رو چاپ کنیم.

در کد بالا اگر هیچ عدد یکتایی وجود نداشته باشه و درواقع لیست uniqueNumbers خالی باشه برنامه با خطا مواجه میشه. برای حل این مشکل می‌تونیم به متد Aggregate مقدار پیشفرض بدیم که در این مسئله عدد ۰ هستش.

var xor = uniqueNumbers.Aggregate(0, (result, nextNumber) => nextNumber ^ result);

کد نهایی:

void PrintXorUniqueNumbers(IEnumerable<int> numbers) {
    var uniqueNumbers = numbers.GroupBy(number => number)
        .Where(group => group.Count() == 1)
        .Select(group => group.Key)
        .ToList();

    var xor = uniqueNumbers.Aggregate(0, (result, nextNumber) => nextNumber ^ result);
    Console.WriteLine(xor);
}

امیدوارم براتون مفید بوده باشه. :)

• اگر دوست داشتین لایک کنید
• لینک مطلب رو برای کسایی که فکر می‌کنید به دردشون میخوره بفرستین
• اگر سوالی هم داشتین همینجا بپرسید

ان‌شاءالله در پناه خدا همیشه صبور، شاد و موفق باشین.