The “Product of Array Except Itself” program is a fundamental algorithmic exercise in the domain of array manipulation and problem-solving. This Java Program aims to transform a given array into a new array where each element is the product of all other elements in the original array except the element at the same index. This seemingly simple task presents an intriguing challenge that requires careful consideration of the array’s elements and strategic algorithm design.
The program involves traversing the array twice while constructing two auxiliary arrays, known as prefix and suffix product arrays. These arrays are instrumental in calculating the products of elements to the left and right of each index, which is then multiplied together to achieve the final product of array elements except the current index. This approach not only showcases how to optimize calculations by utilizing already computed values but also introduces programming enthusiasts to the concept of dynamic element transformations through intermediate data structures.
By understanding and implementing the “Product of Array Except Itself” program, beginners are exposed to essential concepts such as array iteration, prefix and suffix calculations, and the significance of intermediate arrays in algorithmic solutions. This exercise encourages learners to think critically about problem-solving strategies, providing a foundation for more advanced challenges in programming and algorithm design.
Product of Array Except Itself
Ways 1:
This Java program, InterviewPrograms_101_productArrayItself, aims to generate a new array where each element is the product of all elements of the original array except the one at the same index. This is achieved using a technique called “prefix and suffix products.”
package com.softwaretestingo.interviewprograms;
import java.util.Arrays;
public class InterviewPrograms_101_productArrayItself
{
/*
* Write a java program to given array arr [ 1,2,3,4 ] to multiple thee number
* and ignore one for next ignore another one number and continue
* same so we will get out put [ 24,12,8,6 ]
*/
//This Questions Asked in Cigniti technologies
void multipleValue(int arr[], int n)
{
// If Only 1 Element is passed
if (n == 1)
{
System.out.print(0);
return;
}
// Initialize memory to all arrays
int left[] = new int[n];
int right[] = new int[n];
int prod[] = new int[n];
int i, j;
/* Left most element of left array is always 1 */
left[0] = 1;
/* Right most element of right array is always 1 */
right[n - 1] = 1;
/* Construct the left array */
for (i = 1; i < n; i++)
left[i] = arr[i - 1] * left[i - 1];
/* Construct the right array */
for (j = n - 2; j >= 0; j--)
right[j] = arr[j + 1] * right[j + 1];
/* Construct the product array using left[] and right[] */
for (i = 0; i < n; i++)
prod[i] = left[i] * right[i];
/* print the constructed prod array */
for (i = 0; i < n; i++)
System.out.print(prod[i] + " ");
return;
}
public static void main(String[] args)
{
InterviewPrograms_101_productArrayItself pa = new InterviewPrograms_101_productArrayItself();
int arr[] = { 1,2,3,4 };
int n = arr.length;
System.out.println("Inputted Array Is: "+Arrays.toString(arr));
System.out.println("The product array is : ");
pa.multipleValue(arr, n);
}
}
Output:
Inputted Array Is: [1, 2, 3, 4] The product array is : 24 12 8 6
Here’s a step-by-step explanation of the program for Java beginners:
- Import Required Libraries: The program imports the Arrays class from the java.util package to be able to print arrays later.
- Class Definition: The class InterviewPrograms_101_productArrayItself contains the main program logic.
- Method multipleValue: This method calculates the product array based on the input array arr and its length n.
- Handling Edge Case: If the array has only one element, the result is 0, which is printed, and the method returns.
- Arrays Initialization: Three arrays are created: left, right, and prod to store left products, right products, and the final product array, respectively.
- Calculation of Left Products: The left array is constructed where each element is the product of all the elements to its left in the original array.
- Calculation of Right Products: The right array is constructed where each element is the product of all the elements to its right in the original array.
- Construction of Product Array: The prod array is formed by multiplying the corresponding elements of the left and right arrays.
- Printing the Product Array: The program prints the elements of the prod array, which are the desired product values.
- main Method: This is where the program execution starts. An instance of the class is created. An example input array [1, 2, 3, 4] is defined. The input array is displayed, and the multipleValue method is called with the input array and its length.
Through this program, you’re learning how to manipulate arrays and how to calculate products of elements using prefix and suffix techniques. This kind of problem-solving approach is crucial in programming, as it helps in optimizing solutions and understanding algorithmic concepts.
Way 2:
This Java program, InterviewPrograms_101_productArrayItself_1, aims to generate a new array where each element is the product of all elements of the original array except the one at the same index. It employs an alternative approach using two separate loops to achieve the same result as the previous program.
package com.softwaretestingo.interviewprograms;
import java.util.Arrays;
public class InterviewPrograms_101_productArrayItself_1
{
/*
* Write a java program to given array arr [ 1,2,3,4 ] to multiple thee number
* and ignore one for next ignore another one number and continue
* same so we will get out put [ 24,12,8,6 ]
*/
//This Questions Asked in Cigniti technologies
void multipleValue(int arr[], int n)
{
// If Only 1 Element is passed
if (n == 1)
{
System.out.print(0);
return;
}
int i, temp = 1;
/* Allocate memory for the product array */
int prod[] = new int[n];
/* Initialize the product array as 1 */
for (int j = 0; j < n; j++)
prod[j] = 1;
/* In this loop, temp variable contains product of
elements on left side excluding arr[i] */
for (i = 0; i < n; i++)
{
prod[i] = temp;
temp *= arr[i];
}
/* Initialize temp to 1 for product on right side */
temp = 1;
/* In this loop, temp variable contains product of
elements on right side excluding arr[i] */
for (i = n - 1; i >= 0; i--)
{
prod[i] *= temp;
temp *= arr[i];
}
/* print the constructed prod array */
for (i = 0; i < n; i++)
System.out.print(prod[i] + " ");
return;
}
public static void main(String[] args)
{
InterviewPrograms_101_productArrayItself_1 pa = new InterviewPrograms_101_productArrayItself_1();
int arr[] = { 1,2,3,4 };
int n = arr.length;
System.out.println("Inputted Array Is: "+Arrays.toString(arr));
System.out.println("The product array is : ");
pa.multipleValue(arr, n);
}
}
Output:
Inputted Array Is: [1, 2, 3, 4] The product array is : 24 12 8 6
Here’s a concise step-by-step explanation for Java beginners:
- Program Goal: The program’s objective is to transform an input array, such as [1, 2, 3, 4], into an output array where each element is the product of all other elements in the original array. The output for the input [1, 2, 3, 4] would be [24, 12, 8, 6].
- Approach: This version of the program uses two loops to achieve the product calculation. The first loop calculates the product of elements on the left side of the current index, excluding the current element. The second loop then calculates the product of elements on the right side of the current index, excluding the current element, and multiplies it with the previously calculated left-side product.
- Algorithm Steps:
- Initialize temp to 1.
- Create an array prod to store the product values.
- Loop through the array from left to right and calculate the product of elements on the left side of the current index (excluding the current element) and store it in prod.
- Reset temp to 1.
- Loop through the array from right to left and calculate the product of elements on the right side of the current index (excluding the current element), multiply it by the corresponding value in prod, and store it back in prod.
- Printing Results: The program then prints the generated product array, providing the desired output.
- Main Method: The main method initializes the program, creates an instance of the class, defines an example input array, and calls the multipleValue method to perform the product calculation and printing.
Through this version of the program, beginners gain insights into an alternative approach to solving the problem using two separate loops and a temporary variable. This demonstrates the flexibility of problem-solving in programming and showcases different strategies to achieve the same result.
