Given an array arr[], the task is to find the only remaining element in the array after applying the below operation till there is only one element left in the array. In an operation, multiply the boundary elements of this array and if the size of the array is:
- Even: Insert the product in the middle of the array and remove the boundary elements
- Odd: Subtract the middle element from the product and replace the middle element with the absolute difference and remove the boundary elements.
Examples:
Input: arr[] = [ 1, 2, 3, 4, 5, 6 ]
Output: 8
Explanation: See the image below for explanation.
Input: arr[] = [ 3, 5, 1, 8, 9]
Output: 14
Approach: The solution is based on greedy approach. Delete the elements from the ends of the array and insert the data in the middle of the array. Now follow the below steps to solve this problem:
- Run a while loop, till the size of the array arr[] is greater than 1. In each iteration of this loop:
- Take the product of the first and the last elements and then pop them.
- If the size of the array is even, then insert the product in the middle of the array arr[].
- If it is odd then subtract the middle element from the product and replace it with the middle element.
- After the loop ends, print the only remaining element in the array.
C++
// C++ program for the baove approach #include <bits/stdc++.h> using namespace std; // Function to reduce array void PSarray(vector<int> A) { while (A.size() != 1) { // If size of array is Even if (A.size() % 2 == 0) { // Product of boundary element int x = A[0] * A[A.size() - 1]; A.erase(A.begin()); A.pop_back(); int n = A.size(); // Insert product in middle of element A.insert(A.begin() + n / 2, x); } // Else if size of array is Odd else { int x = A[0] * A[A.size() - 1]; A.erase(A.begin()); A.pop_back(); int n = A.size(); // Subtract middle element from product and // replace middle element A[n / 2] = x - A[n / 2]; } } // Print the last remaining array element cout << A[0] << endl; } // Driver Code int main() { vector<int> arr = { 1, 2, 3, 4, 5, 6 }; PSarray(arr); return 0; } // This code is contributed by Tapesh (tapeshdua420) |
Java
// Java program for the baove approach import java.util.ArrayList; import java.util.Arrays; class GFG { // Function to reduce array static void PSarray(ArrayList<Integer> A) { while (A.size() != 1) { // If size of array is Even if (A.size() % 2 == 0){ // Product of boundary element int x = A.get(0)*A.get(A.size()-1); A.remove(0); A.remove(A.size() - 1); int n = A.size(); // Insert product in middle of element A.add(n/2, x); } // Else if size of array is Odd else { int x = A.get(0)*A.get(A.size() - 1); A.remove(0); A.remove(A.size() - 1); int n = A.size(); // Subtract middle element from product and // replace middle element A.set(n / 2, x - A.get(n / 2)); } } // Print the last remaining array element System.out.println(A); } // Driver Code public static void main(String[] args) { Integer []arr = {1, 2, 3, 4, 5, 6}; ArrayList<Integer> A = new ArrayList<>(Arrays.asList(arr)); PSarray(A); } } // This code is contributed by shikhasingrajput |
Python3
# Python program for the baove approach # Function to reduce array def PSarray(A): while len(A) != 1: # If size of array is Even if len(A) % 2 == 0: # Product of boundary element x = A.pop(0)*A.pop() n = len(A) # Insert product in middle of element A.insert(n//2, x) # Else if size of array is Odd else: x = A.pop(0)*A.pop() n = len(A) # Subtract middle element from product and # replace middle element A[n//2] = x-A[n//2] # Print the last remaining array element print(A[0]) # Driver Code if __name__ == "__main__": A = [1, 2, 3, 4, 5, 6] PSarray(A) |
C#
// C# program for the baove approach using System; using System.Collections.Generic; public class GFG { // Function to reduce array static void PSarray(List<int> A) { while (A.Count != 1) { // If size of array is Even if (A.Count % 2 == 0){ // Product of boundary element int x = A[0]*A[A.Count-1]; A.RemoveAt(0); A.RemoveAt(A.Count - 1); int n = A.Count; // Insert product in middle of element A.Insert(n/2,x); } // Else if size of array is Odd else { int x = A[0]*A[A.Count - 1]; A.RemoveAt(0); A.RemoveAt(A.Count - 1); int n = A.Count; // Subtract middle element from product and // replace middle element A[n / 2] = x - A[n / 2]; } } // Print the last remaining array element A.ForEach(x=>Console.Write(x)); } // Driver Code public static void Main(String[] args) { int []arr = {1, 2, 3, 4, 5, 6}; List<int> A = new List<int>(arr); PSarray(A); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the baove approach // Function to reduce array function PSarray(A) { while (A.length != 1) { // If size of array is Even if (A.length % 2 == 0) { // Product of boundary element let x = A.shift() * A.pop() let n = A.length // Insert product in middle of element let p1 = A.slice(0, Math.floor(A.length / 2)) p1.push(x) let p2 = A.slice(Math.floor(A.length / 2)) A = p1.concat(p2) } // Else if size of array is Odd else { let x = A.shift() * A.pop() let n = A.length // Subtract middle element from product and // replace middle element A[(Math.floor(n / 2))] = x - A[(Math.floor(n / 2))] } // Print the last remaining array element } document.write(A[0]) } // Driver Code let A = [ 1, 2, 3, 4, 5, 6 ] PSarray(A) // This code is contributed by Potta Lokesh </script> |
Output
8
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
