LCS-Zero – প্রোগ্রামিং ইন্টারভিউ সমস্যা ১২

সমস্যাঃ একটা ইন্টিজারের অ্যারে দেওয়া আছে। সেখানে যদি পরপর কতগুলো সংখ্যা পাওয়া যায়, যাদের সমষ্টি শূন্য, সেই সংখ্যাগুলোর মধ্যে সবচেয়ে বেশিসংখ্যক ক্রমিক (অ্যারেতে ক্রমানুসারে সাজানো) সংখ্যাগুলো বের করতে হবে।

উদাহরণঃ 1, 2, -2, 4, -4 – এই সংখ্যাগুলোর মধ্যে, 2, -2 -এর যোগফল 0; 4, -4 – এর যোগফল 0; আবার 2, -2, 4, -4 সংখ্যাগুলোর যোগফলও 0। এখন সবচেয়ে বেশি সংখ্যক ক্রমিক সংখ্যা হচ্ছে 2, -2, 4, -4। তাই আমাদের উত্তর হবে 2, -2, 4, -4.

সমস্যাটি কেউ নিজে সমাধান করতে চাইলে এখানে চেষ্টা করতে হবে – https://www.interviewbit.com/problems/largest-continuous-sequence-zero-sum/

সমাধানঃ আমরা প্রথমে সবচেয়ে সহজ বুদ্ধি প্রয়োগ করতে পারি। অ্যারেতে যদি n সংখ্যক উপাদান থাকে, তাহলে সবগুলো উপাদানের সমষ্টি 0 কী না, সেটি পরীক্ষা করি। তারপরে n-1 সংখ্যক ক্রমিক সংখ্যার সমষ্টি 0 কী না পরীক্ষা করি। তারপর n-2 সংখ্যক ক্রমিক সংখ্যার সমষ্টি পরীক্ষা করি… এভাবে যতক্ষণ না আমরা সমষ্টি 0 পাচ্ছি, ততক্ষণ পরীক্ষা করবো আর n-এর মান এক কমাতে থাকবো 1 পর্যন্ত। যেমন, আমাদের যদি 1, 2, 3, -4, 5 – এই পাঁচটি সংখ্যা দেওয়া হয়, তাহলে প্রথমে পরীক্ষা করবো –

1 + 2 + 3 + -4 + 5 = 7

তারপরে চারটি করে ক্রমিক সংখ্যা নেব –
1 + 2 + 3 + -4 = 2
2 + 3 + -4 + 5 = 6

এবারে তিনটি করে ক্রমিক সংখ্যা –
1 + 2 + 3 = 6
2 + 3 + -4 = 1
3 + -4 + 5 = 4

এখন দুটি করে ক্রমিক সংখ্যা নেই –
1 + 2 = 3
2 + 3 = 5
3 + -4 = -1
-4 + 5 = 1

এখন একটি করে সংখ্যা নিয়ে দেখবো তাদের সমষ্টি (অর্থাৎ সেই সংখ্যাটির মান) 0 কী না। এই উদাহরণে এরকম সংখ্যা নাই।

যাই হোক, আশা করি, আমি কী করতে চাচ্ছি, তা বুঝাতে পেরেছি। এখন নিজে কোড লেখার চেষ্টা করতে হবে।

আমরা এরকম কোড লিখতে পারি –

def lszero1(A):
    n = len(A)
    
    for window_size in range(n, 0, -1):
        for start in range(0, n):
            if start+window_size > n:
                    break
            if 0 == sum(A[start:start+window_size]):
                return A[start:start+window_size]
                
    return []

এই কোডের কমপ্লেক্সিটি কত? sum() ফাংশনের কমপ্লেক্সিটি হচ্ছে O(n)। তাহলে আমাদের ফাংশনের কমপ্লেক্সিটি হবে O(n^3). প্রতিবার কিন্তু আসলে sum() ফাংশন ব্যবহার না করলেও চলে। আমরা যদি জানি, 1 + 2 + 3 = 6, তাহলে 2 + 3 + 4 হবে, আগের যোগফল থেকে 1 বিয়োগ ও 4 যোগ। বিষয়টি একটু ঠান্ডা মাথায় চিন্তা করলেই বুঝে ফেলার কথা। এই কাজটি ঠিকভাবে করতে পারলে আমরা আমাদের কোডের কমপ্লেক্সিটি O(n^2)-এ নামিয়ে আনতে পারবো।

for window_size in range(n, 0, -1):
    w_sum = sum(A[0:window_size])
    if w_sum == 0:
        return A[0:window_size]
    for start in range(1, n):
        if start + window_size > n:
            break    
        w_sum = w_sum - A[start-1] + A[start+window_size-1]
        if w_sum == 0:
            return A[start:start+window_size]                

এখন, আরো গভীরভাবে চিন্তা করলে, এই সমস্যাটির সমাধান O(n) কমপ্লেক্সিটিতেও করা সম্ভব। এবং 90% ক্ষেত্রে ইন্টারভিউয়ার হয়ত সেটিই আশা করবেন, কিংবা বলে দিবেন যে O(n) কমপ্লেক্সিটিতে সমাধান করতে। সেটি নিজে করার চেষ্টা করতে হবে। আমি কেবল একট হিন্ট দিয়ে দিচ্ছি –

A = [1, 2, -2, 4, -4], এর শুরু থেকে ক্রমিক সংখ্যাগুলোর যোগফল 1, 3 (1+2), 1 (1+2+-2), 5 , (1+2+-2+4), 1 (1+2+-2+4+-4)। এগুলো একটি অ্যারেতে রাখি –
S = [1, 3, 1, 5, 1]. এখন এই ক্ষেত্রে, প্রথম সংখ্যাটি 1, আবার পঞ্চম সংখ্যাটিও 1। অর্থাৎ প্রথম সংখ্যার পরে পরপর চারটি সংখ্যা যোগ করে যোগফলের কোনো পরিবর্তন হলো না। এতে আমরা কী বুঝলাম?

Facebook Comments

Leave a Reply