একটি নন-ডিক্রিজিং (non-decreasing) পজিটিভ ইন্টিজার অ্যারে nums এবং একটি ইন্টিজার K দেওয়া আছে। চেক করতে হবে এই অ্যারেটি এক বা অধিক ডিসজয়েন্ট (disjoint) ক্রমবর্ধমান সাবসিকোয়েন্সে ভাগ করা যায় কিনা, যাতে প্রতিটি সাবসিকোয়েন্সের দৈর্ঘ্য কমপক্ষে K হয়।
যেমন, nums = [1,2,2,3,3,4,4], K = 3 হলে আউটপুট true, কারণ এটি দুটি সাবসিকোয়েন্সে ভাগ করা যায়: [1,2,3,4] এবং [2,3,4] — দুটির দৈর্ঘ্য কমপক্ষে ৩।
প্রতিটি সংখ্যার ফ্রিকোয়েন্সি কাউন্ট করা।
সর্বোচ্চ ফ্রিকোয়েন্সি (req) বের করা।
যদি req * K <= len(nums) হয়, তবে সম্ভব।
কারণ: সবচেয়ে বেশি বার যেটি আসছে, সেটি আলাদা আলাদা সাবসিকোয়েন্সে যেতে হবে। তাই কমপক্ষে req টি সাবসিকোয়েন্স লাগবে। প্রতিটির দৈর্ঘ্য K হলে মোট req*K উপাদান লাগবে।
class Solution(object):
def canDivideIntoSubsequences(self, nums, K):
d = {}
req = 0
for i in nums:
if i not in d:
d[i] = 1
else:
d[i] += 1
req = max(req, d[i])
return req * K <= len(nums)
ob = Solution()
print(ob.canDivideIntoSubsequences([1, 2, 2, 3, 3, 4, 4], 3))
[1, 2, 2, 3, 3, 4, 4], 3
True
