C++ में प्रोडक्ट ऐरे पजल (अतिरिक्त स्पेस के साथ)

यहां हम ऐरे से संबंधित एक रोचक समस्या देखेंगे। n तत्वों वाला एक ऐरे है। हमें n तत्वों का एक और ऐरे बनाना है। लेकिन दूसरे ऐरे का i-th स्थान पहले ऐरे के i-th तत्व को छोड़कर सभी तत्वों का गुणनफल रखेगा। और एक प्रतिबंध है कि हम इस समस्या में भाग ऑपरेटर का उपयोग नहीं कर सकते।

यदि हम भाग ऑपरेशन का उपयोग कर सकते हैं, तो हम इस समस्या को आसानी से हल कर सकते हैं, सभी तत्वों का गुणनफल प्राप्त करके, फिर पहले ऐरे के i-th तत्व से भाग देकर दूसरे ऐरे के i-th स्थान में स्टोर कर सकते हैं।

यहां हम दो अलग ऐरे बनाकर हल कर रहे हैं - left और right। left[i] में array[i] के बाईं ओर के सभी तत्वों का गुणनफल होगा (array[i] को छोड़कर), और right[i] में arr[i] के दाईं ओर के सभी तत्वों का गुणनफल होगा (arr[i] को छोड़कर)। यह समाधान O(n) समय लेगा। लेकिन यह अतिरिक्त स्पेस लेगा।

एल्गोरिदम

productArray(arr, n)

begin
    आकार n के दो ऐरे left और right परिभाषित करें
    आकार n का res नामक एक ऐरे परिभाषित करें
    left का पहला तत्व और right का अंतिम तत्व 1 सेट करें
    for i in range 1 to n, do
        left[i] = left[i-1] * arr[i-1]
    done
    for i in range n-1 down to 1, do
        right[i] = right[i+1] * arr[i+1]
    done
    for i in range 1 to n, do
        res[i] = left[i] * right[i];
    done
    return res
end

उदाहरण

#include <iostream>
using namespace std;

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void productArray(int arr[], int product[], int n) {
    // left right ऐरे बनाएं
    int *left = new int[n];
    int *right = new int[n];
    
    // left[] के पहले तत्व और right[] के अंतिम तत्व को 1 सेट करें
    left[0] = right[n-1] = 1;
    
    for (int i = 1; i < n; i++) {
        left[i] = left[i-1] * arr[i-1];
    }
    
    for (int i = n-2; i >= 0; i--) {
        right[i] = right[i+1] * arr[i+1];
    }
    
    // left और right ऐरे का उपयोग करके प्रोडक्ट ऐरे प्राप्त करें
    for (int i = 0; i < n; i++) {
        product[i] = left[i] * right[i];
    }
    
    delete[] left;
    delete[] right;
}

int main() {
    int myArr[7] = {5, 4, 7, 6, 9, 2, 3};
    int resArr[7];
    cout << "Initial Array: ";
    printArray(myArr, 7);
    productArray(myArr, resArr, 7);
    cout << "Final Array: ";
    printArray(resArr, 7);
    return 0;
}

आउटपुट

Initial Array: 5 4 7 6 9 2 3
Final Array: 9072 11340 6480 7560 5040 22680 15120