ধরি একটি অঙ্কের অ্যারে দেওয়া আছে। আমাদের দেওয়া অঙ্কগুলোর যেকোনো ক্রমে সংযোজিত করে তিন দ্বারা ভাজ্য সর্বোচ্চ সংখ্যা বের করতে হবে। উত্তর খুব বড় হতে পারে তাই এটি স্ট্রিং আকারে ফেরত দিতে হবে। যদি কোনো উত্তর না থাকে তবে খালি স্ট্রিং ফেরত দিন।
ইনপুট যদি হয় [7,2,8], তবে আউটপুট হবে 87।
সমাধানের ধাপসমূহ
d নামক একটি 2D অ্যারে সংজ্ঞায়িত করুন, যাতে তিনটি সারি থাকবে
digits অ্যারেটি সোর্ট করুন
sum := 0
i := 0 থেকে digits এর আকার পর্যন্ত লুপ চালান –
x := digits[i]
digits[i] কে d[x mod 3]-এর শেষে যোগ করুন
sum := sum + x
sum := sum mod 3
যদি sum নন-জিরো হয়, তবে –
যদি d[sum] এর আকার 0 হয়, তবে –
rem := 3 - sum
যদি d[rem] এর আকার < 2 হয়, তবে –
খালি স্ট্রিং ফেরত দিন
d[rem]-এর শেষ উপাদান দুবার মুছে দিন
অন্যথায় –
d[sum]-এর শেষ উপাদান মুছে দিন
ret := খালি স্ট্রিং
i := 0 থেকে 2 পর্যন্ত লুপ চালান –
j := 0 থেকে d[i] এর আকার পর্যন্ত লুপ চালান –
ret := ret + d[i, j] স্ট্রিং আকারে
ret অ্যারেটি সোর্ট করুন (অবরোহক্রমে)
যদি ret-এর আকার > 0 এবং ret[0] == '0' হয়, তবে –
"0" ফেরত দিন
ret ফেরত দিন
বेहतर বোঝার জন্য নিচের কোডটি দেখুন –
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: string largestMultipleOfThree(vector<int>& digits) { vector<vector<int>> d(3); sort(digits.begin(), digits.end(), greater<int>()); int sum = 0; for (int i = 0; i < digits.size(); i++) { int x = digits[i]; d[x % 3].push_back(digits[i]); sum += x; sum %= 3; } if (sum) { if (!d[sum].size()) { int rem = 3 - sum; if (d[rem].size() < 2) return ""; d[rem].pop_back(); d[rem].pop_back(); } else { d[sum].pop_back(); } } string ret = ""; for (int i = 0; i < 3; i++) { for (int j = 0; j < d[i].size(); j++) { ret += to_string(d[i][j]); } } sort(ret.begin(), ret.end(), greater<int>()); if (ret.size() && ret[0] == '0') return "0"; return ret; } }; main(){ Solution ob; vector<int> v = {7,2,8}; cout << (ob.largestMultipleOfThree(v)); }ইনপুট
{7,2,8}আউটপুট
87
