৪টি অঙ্কের একটি অ্যারে দেওয়া আছে। আমাদের সেই অঙ্কগুলো দিয়ে সম্ভাব্য সর্বোচ্চ ২৪-ঘন্টার সময় বের করতে হবে। ছোটতম সময় ০০:০০ এবং সর্বোচ্চ ২৩:৫৯। ০০:০০ থেকে শুরু করে যে সময়টি বেশি সময় বিতাল করবে সেটিই বড়। উত্তরটি ৫ অক্ষরের স্ট্রিং হিসেবে রিটার্ন করতে হবে। কোনো বৈধ সময় না থাকলে খালি স্ট্রিং রিটার্ন করবে।
ইনপুট [1,2,3,4] হলে আউটপুট "23:41"।
সমাধানের ধাপসমূহ
- isValid() ফাংশন: সময় স্ট্রিং বৈধ কিনা চেক করুন
- dfs() ফাংশন: ব্যাকট্র্যাকিং দিয়ে সব পারমুটেশন চেক করুন
- মূল ফাংশন থেকে dfs কল করে সর্বোচ্চ বৈধ সময় রিটার্ন করুন
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void dfs(vector<int>& A, string& res, string& cur) {
if (cur.size() == 5) {
if (isValid(cur) && cur > res)
res = cur;
return;
}
for (int i = 0; i < 4; ++i) {
if (A[i] != -1) {
int tmp = A[i];
cur += A[i] + '0';
if (cur.size() == 2)
cur += ':';
A[i] = -1;
dfs(A, res, cur);
A[i] = tmp;
cur.pop_back();
if (cur.size() == 2)
cur.pop_back();
}
}
}
bool isValid(const string a) {
if (a[0] > '2') return false;
if (a[0] == '2' && a[1] > '3') return false;
if (a[3] > '5') return false;
return true;
}
string largestTimeFromDigits(vector<int>& A) {
string res = "", tmp = "";
dfs(A, res, tmp);
return res;
}
};
int main(){
Solution ob;
vector<int> v = {1,2,3,4};
cout << (ob.largestTimeFromDigits(v));
}ইনপুট
{1,2,3,4}আউটপুট
23:41
