Replace Array Elements - C++ Solution

1. Introduction

The "Replace Array Elements" problem is a typical interview question that tests a candidate's ability to manipulate arrays in a creative way. The challenge is to replace each element in an array with the product of all other elements without using the division operator, which requires a careful approach to avoid directly calculating each product.

Problem

Given an integer array, the objective is to replace each element with the product of every other element in the array. The solution should be implemented in-place and should not use the division operator. This requires a strategy to efficiently calculate the product of all elements except the current one for each position in the array.

2. Solution Steps

1. Create two temporary arrays, left and right, of the same size as the input array. left[i] will store the product of all elements to the left of i, and right[i] will store the product of all elements to the right of i.

2. Fill the left array with cumulative products from the left, and the right array with cumulative products from the right.

3. Replace each element in the original array with the product of its corresponding left and right values.

4. This approach ensures that each position in the array gets the product of all other elements without direct multiplication.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to replace each element with the product of every other element
void replaceElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> left(n, 1), right(n, 1);

    // Compute the left product for each element
    for (int i = 1; i < n; i++) {
        left[i] = nums[i - 1] * left[i - 1];
    }

    // Compute the right product for each element
    for (int i = n - 2; i >= 0; i--) {
        right[i] = nums[i + 1] * right[i + 1];
    }

    // Replace each element with the product of its left and right products
    for (int i = 0; i < n; i++) {
        nums[i] = left[i] * right[i];
    }
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    replaceElements(nums);

    // Print the modified array
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

120 60 40 30 24

Explanation:

The function replaceElements first calculates the product of elements to the left and right of every element by using two additional arrays left and right. 

It then iterates over the array to replace each element with the product of its corresponding values in left and right. 

This approach effectively calculates the desired product for each element without using division, and it maintains the constraint of in-place modification.