পাইথনে ক্যান্ডি বিতরণ (Distribute Candies to People in Python)

সমস্যা বিবরণ

n জন লোকের মাঝে ক্যান্ডি বিতরণ করতে হবে:

1. ১লা লোক পাবে ১ ক্যান্ডি, ২রা ২, ..., n-তম লোক পাবে n ক্যান্ডি।
2. পুনরাবৃত্তি: ১লা লোক পাবে n+1, ২রা n+2, ..., n-তম লোক পাবে 2n।
3. ক্যান্ডি শেষ হওয়া পর্যন্ত এভাবে চলবে। শেষ ব্যক্তি বাকি সব ক্যান্ডি পাবে।

উদাহরণ: ক্যান্ডি=৭, n=৩ → [2,2,3] (১লা:১, ২রা:২, ৩রা:৩, ১লা:১ → মোট ২,২,৩)।

সমাধানের পদ্ধতি

1. n সাইজের অ্যারে ০ দিয়ে ইনিশিয়ালাইজ করুন।
2. index = 0 থেকে শুরু করুন।
3. ক্যান্ডি থাকা পর্যন্ত:
   • current_person = index % n
   • give = min(ক্যান্ডি, index + 1)
   • res[current_person] += give
   • ক্যান্ডি -= give
   • index += 1
4. রেজাল্ট ফেরত দিন।

পাইথন উদাহরণ

class Solution(object):
    def distributeCandies(self, candies, num_people):
        res = [0] * num_people
        index = 0
        while candies > 0:
            give = min(candies, index + 1)
            res[index % num_people] += give
            candies -= give
            index += 1
        return res

ob1 = Solution()
print(ob1.distributeCandies(8, 3))

ইনপুট

8 3

আউটপুট

[3, 2, 3]

গাণিতিক অপ্টিমাইজেশন (O(√candies))

import math

def distributeCandies(candies, num_people):
    res = [0] * num_people
    # পূর্ণ রাউন্ড কতটা?
    k = int((math.sqrt(1 + 8*candies) - 1) // 2)
    full_rounds = k // num_people
    remaining = k % num_people
    
    for i in range(num_people):
        # প্রতিটি ব্যক্তির পূর্ণ রাউন্ডে মোট ক্যান্ডি
        res[i] = (i + 1) * full_rounds + num_people * full_rounds * (full_rounds - 1) // 2
        # বাকি রাউন্ডে
        if i < remaining:
            res[i] += i + 1 + full_rounds * num_people
    
    # শেষ বাকি ক্যান্ডি
    remaining_candies = candies - k * (k + 1) // 2
    if remaining_candies > 0:
        res[remaining] += remaining_candies
    return res