সার্কুলার ট্র্যাকে সবচেয়ে বেশি ভিজিট করা সেক্টর বের করা

একটি n সেক্টরের সার্কুলার ট্র্যাক আছে (১ থেকে n লেবেল, কাউন্টার-ক্লকওয়াইজ)। rounds অ্যারে দেওয়া আছে। i-তম রাউন্ড rounds[i-1] সেক্টর থেকে শুরু হয় rounds[i]-এ শেষ হয়। সবচেয়ে বেশি ভিজিট করা সেক্টরগুলো অ্যাসেন্ডিং অর্ডারে রিটার্ন করতে হবে।

ইনপুট: n = 4, rounds = [1,3,1,2] → আউটপুট: [1, 2]।

ভিজিট সিকোয়েন্স: ১→২→৩ (১ম রাউন্ড শেষ) → ৪→১ (২য় রাউন্ড শেষ) → ২ (৩য় রাউন্ড শেষ)। সেক্টর ১ ও ২ দুইবার ভিজিট হয়েছে (সর্বোচ্চ)।

সমাধানের ধাপসমূহ

• d := ডিকশনারি (সেক্টর → ভিজিট কাউন্ট), ১ থেকে n পর্যন্ত ০ দিয়ে ইনিশিয়ালাইজ

• d[rounds[0]] = 1

• i = 1 থেকে len(rounds)-1:

  • যদি rounds[i] > rounds[i-1]: rounds[i-1]+1 থেকে rounds[i] পর্যন্ত d[j]++
  • অন্যথায়: rounds[i-1]+1 থেকে n পর্যন্ত d[j]++, তারপর ১ থেকে rounds[i] পর্যন্ত d[j]++

• curr = d[rounds[0]], out = [rounds[0]]

• i = 1 থেকে n:

  • যদি i != rounds[0]:
    • যদি d[i] > curr: curr = d[i], out = [i]
    • যদি d[i] == curr: out.append(i)

• sorted(out) রিটার্ন করুন

উদাহরণ (Python)

def solve(n, rounds):
    d = {}
    for j in range(1, n+1):
        d[j] = 0
    d[rounds[0]] = 1
    for i in range(1, len(rounds)):
        if rounds[i] > rounds[i-1]:
            for j in range(rounds[i-1]+1, rounds[i]+1):
                d[j] += 1
        else:
            for j in range(rounds[i-1]+1, n+1):
                d[j] += 1
            for j in range(1, rounds[i]+1):
                d[j] += 1
    curr = d[rounds[0]]
    out = [rounds[0]]
    for i in range(1, n+1):
        if i != rounds[0]:
            if d[i] > curr:
                curr = d[i]
                out = [i]
            elif d[i] == curr:
                out = out + [i]
    return sorted(out)

n = 4
rounds = [1, 3, 1, 2]
print(solve(n, rounds))

ইনপুট

4, [1,3,1,2]

আউটপুট

[1, 2]