Check if final remainder is present in original Array by reducing it based on given conditions
Given an array arr[] of Natural numbers, the task is to remove one element from front and one element from end and find their product and then divide the product by middle element of the array and append remainder we got in the end of the array and continue the same operation until size of array becomes 2.
Now when at last array contains only two elements then product of both elements is divided by the size of the original array and we have to print “YES” if remainder is present in the original array otherwise “NO”.
Example:
Input: arr[] = {2, 3, 4, 6, 3, 7}
Output: NO
Explanation:
Following are the operations performed on the given array elements:
Pop element from front and rear and divide it by middle and insert remainder into array from rear.
1. mid = 6, front = 2, rear = 7 remainder will be (2*7) % 6 = 2 modifies the array to arr={3, 4, 6, 3, 2}
2. mid = 6, front = 3, rear = 2 remainder will be (3*2) % 6 = 0 modifies the array to arr={4, 6, 3, 0}
3. mid = 3, front = 4, rear = 0 remainder will be (4*0) % 3 = 0 modifies the array to arr={6, 3, 0}
4. mid = 3, front = 6, rear = 0 remainder will be (6*0) % 3 = 0 modifies the array to arr={3, 0}
After the following operations size of arr=2 so (3*0) % 6 = 0, and 0 is not in arr so return “NO”
Input: arr[] = [2, 3, 4, 8, 5, 7]
Output: YES
Reduced array will be [5, 4]
(5 * 4) % 6 = 2, which is present in Array, so return “YES”
Naive Approach:
- Take mid as Middle element of the array.
- Pop element from front and rear, take the product of it and divide the product by the middle element. (popping out element form the front takes O(N) time).
- Insert remainder into an array from the rear, continue it till the size of the array becomes 2.
- Now Divide the product of elements by the size of the original array and check remainder is present in the original array or not.
Below are the steps to implement the above approach:
- Copy original array to another array, and perform operation on array.
- Take mid as middle element, pop element from front and rear, take its product and divide it by mid.
- Append the remainder we got after dividing into array from rear.
- Repeat Step 2 until length of array become equal to 2.
- At last, take product of remaining element and divide it by n.
- If remainder is present in original array print “YES” otherwise print “NO”.
Below is the implementation of the above algorithm.
C++
#include <bits/stdc++.h> using namespace std; int Reduced(vector< int > a, int n) { // copying original array vector< int > original_array; original_array = a; // loop till length of array become 2. while (a.size() != 2) { // find middle element int mid = a.size() / 2; int mid_ele = a[mid]; // pop element from front and rear int start = a[0]; a.erase(a.begin()); int end = a[a.size() - 1]; a.pop_back(); // find remainder int rmd = (start * end) % mid_ele; // append remainder to a a.push_back(rmd); // now since length of array is 2 // take product and divide it by n int remainder = (a[0] * a[1]) % n; // if remainder is present is original array // return 1, else return 0 for ( int i = 0; i < original_array.size(); i++) { if (original_array[i] == remainder) { return 1; } } } return 0; } int main() { vector< int > Arr = {2, 3, 4, 8, 5, 7}; int N = Arr.size(); // calling function Reduced int x = Reduced(Arr, N); // if x = 1 print YES else NO if (x) cout << ( "YES" ); else cout << ( "NO" ); return 0; } // This code is contributed by Potta Lokesh |
Java
import java.util.*; class GFG { static int Reduced(Vector<Integer> a, int n) { // copying original array Vector<Integer> original_array = new Vector<>(); original_array = a; // loop till length of array become 2. while (a.size() != 2 ) { // find middle element int mid = a.size() / 2 ; int mid_ele = a.get(mid); // pop element from front and rear int start = a.get( 0 ); a.remove( 0 ); int end = a.get(a.size() - 1 ); a.remove(a.size() - 1 ); // find remainder int rmd = (start * end) % mid_ele; // append remainder to a a.add(rmd); // now since length of array is 2 // take product and divide it by n int remainder = (a.get( 0 ) * a.get( 1 )) % n; // if remainder is present is original array // return 1, else return 0 for ( int i = 0 ; i < original_array.size(); i++) { if (original_array.get(i) == remainder) { return 1 ; } } } return 0 ; } public static void main(String[] args) { int [] arr = { 2 , 3 , 4 , 8 , 5 , 7 }; int N = arr.length; Vector<Integer> Arr = new Vector<>(); for ( int i = 0 ; i < N; i++) Arr.add(arr[i]); // calling function Reduced int x = Reduced(Arr, N); // if x = 1 print YES else NO if (x == 1 ) System.out.print( "YES" ); else System.out.print( "NO" ); } } // This code is contributed by Rajput-Ji |
Python3
# Python program to implement above approach def Reduced(a, n): # copying original array original_array = a[:] # loop till length of array become 2. while len (a) ! = 2 : # find middle element mid = len (a) / / 2 mid_ele = a[mid] # pop element from front and rear start = a.pop( 0 ) end = a.pop() # find remainder rmd = (start * end) % mid_ele # append remainder to a a.append(rmd) # now since length of array is 2 # take product and divide it by n remainder = (a[ 0 ] * a[ 1 ]) % n # if remainder is present is original array # return 1, else return 0 if remainder in original_array: return 1 return 0 Arr = [ 2 , 3 , 4 , 8 , 5 , 7 ] N = len (Arr) # calling function Reduced x = Reduced(Arr, N) # if x = 1 print YES else NO if x: print ( "YES" ) else : print ( "NO" ) |
C#
using System; using System.Collections.Generic; class GFg { static int Reduced(List< int > a, int n) { // copying original array List< int > original_array = new List< int >(a); // loop till length of array become 2. while (a.Count != 2) { // find middle element int mid = a.Count / 2; int mid_ele = a[mid]; // pop element from front and rear int start = a[0]; a.RemoveAt(0); int end = a[a.Count - 1]; a.RemoveAt(a.Count - 1); // find remainder int rmd = (start * end) % mid_ele; // append remainder to a a.Add(rmd); // now since length of array is 2 // take product and divide it by n int remainder = (a[0] * a[1]) % n; // if remainder is present is original array // return 1, else return 0 for ( int i = 0; i < original_array.Count; i++) { if (original_array[i] == remainder) { return 1; } } } return 0; } // Driver code public static void Main() { List< int > Arr = new List< int >() { 2, 3, 4, 8, 5, 7 }; int N = Arr.Count; // calling function Reduced int x = Reduced(Arr, N); // if x = 1 print YES else NO if (x > 0) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } } // This code is contributed by ukasp. |
Javascript
<script> function Reduced(a, n) { // copying original array let original_array = []; original_array = a; // loop till length of array become 2. while (a.length != 2) { // find middle element let mid = Math.floor(a.length / 2); let mid_ele = a[mid]; // pop element from front and rear let start = a[0]; a.shift(); let end = a[a.length - 1]; a.pop(); // find remainder let rmd = (start * end) % mid_ele; // append remainder to a a.push(rmd); // now since length of array is 2 // take product and divide it by n let remainder = (a[0] * a[1]) % n; // if remainder is present is original array // return 1, else return 0 for (let i = 0; i < original_array.length; i++) { if (original_array[i] == remainder) { return 1; } } } return 0; } // Driver code let Arr = [2, 3, 4, 8, 5, 7]; let N = Arr.length; // calling function Reduced let x = Reduced(Arr, N); // if x = 1 print YES else NO if (x) document.write( "YES" ); else document.write( "NO" ); // This code is contributed by gfgking. </script> |
YES
Time Complexity: O(N^2)
Auxiliary Space: O(N)
Efficient Approach (Using Two pointer Algorithm):
- Take start as 0 and end as n-1 and find the middle index by taking the sum of start and end and divide it by 2.
- Find remainder after the operation and replace the last element with the remainder
- continue to do above operations till start becomes equal to end-1.
- Now the array will be having two elements remaining, take the elements of arr and divide its product by n and check the remainder is present in the original array or not.
Below are the steps to implement the above approach:
- Copy original array to another array, and perform operation on array.
- Initial start as 0 and end as n-1
- Find middle index as sum of start and end divided by 2.
- Find remainder by multiplying start and end element, divided by middle element.
- Replacing end element by remainder, Increment start by 1 keeping end same as n-1.
- Repeat step 3 until start become equal to end-1.
- Take product of elements at index start and end of the array and divide it by n.
- If remainder is present in original array print “YES” otherwise “NO”.
below is the implementation for the same
C++
// c++ code for the above implementation #include <iostream> using namespace std; // function definition bool isRemainderPresent( int arr[], int n) { int copyArr[n]; // copying array elements for ( int i = 0; i < n; i++) { copyArr[i] = arr[i]; } int start = 0, end = n - 1; while (start < end - 1) { // Finding middle index as sum of start and end // divided by 2. int middle = (start + end) / 2; // Find remainder by multiplying start and end // element, divided by middle element. // Replacing end element by remainder, Increment // start by 1 keeping end same as n-1. int remainder = (arr[start] * arr[end]) % copyArr[middle]; copyArr[end] = remainder; start++; } // If remainder is present in the array print “YES” // otherwise “NO”. int product = (arr[start] * arr[end]) / n; for ( int i = 0; i < n; i++) { if (copyArr[i] == product % n) { return true ; } } return false ; } int main() { int arr[] = { 2, 3, 4, 8, 5, 7 }; int n = sizeof (arr) / sizeof (arr[0]); if (isRemainderPresent(arr, n)) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; } |
Java
// java code for the above approach import java.util.*; public class GFG { public static boolean isRemainderPresent( int [] arr, int n) { int [] copyArr = Arrays.copyOf(arr, n); int start = 0 , end = n - 1 ; while (start < end - 1 ) { int middle = (start + end) / 2 ; // Finding middle index as sum of start and end // divided by 2. // Find remainder by multiplying start and end // element, // divided by middle element. // Replacing end element by remainder, Increment // start by 1 // keeping end same as n-1. int remainder = (arr[start] * arr[end]) % copyArr[middle]; copyArr[end] = remainder; start++; } // If remainder is present in the array print “YES” // otherwise “NO”. int product = (arr[start] * arr[end]) / n; for ( int i = 0 ; i < n; i++) { if (copyArr[i] == product % n) { return true ; } } return false ; } public static void main(String[] args) { int [] arr = { 2 , 3 , 4 , 8 , 5 , 7 }; int n = arr.length; if (isRemainderPresent(arr, n)) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } } |
Python3
# python code for the above implementation def is_remainder_present(arr, n): # copying array elements copy_arr = arr.copy() start = 0 end = n - 1 while start < end - 1 : # Finding middle index as sum of start and end divided by 2. # Find remainder by multiplying start and end element, # divided by middle element. # Replacing end element by remainder, Increment start by 1 # keeping end same as n-1. middle = (start + end) / / 2 remainder = (arr[start] * arr[end]) % copy_arr[middle] copy_arr[end] = remainder start + = 1 product = (arr[start] * arr[end]) / / n for i in range (n): if copy_arr[i] = = product % n: return True return False arr = [ 2 , 3 , 4 , 8 , 5 , 7 ] n = len (arr) if is_remainder_present(arr, n): print ( "YES" ) else : print ( "NO" ) |
C#
// C# code for the above approach using System; public class GFG { static bool IsRemainderPresent( int [] arr, int n) { int [] copyArr = new int [n]; // copying array elements for ( int i = 0; i < n; i++) { copyArr[i] = arr[i]; } int start = 0, end = n - 1; while (start < end - 1) { // Finding middle index as sum of start and end // divided by 2. int middle = (start + end) / 2; // Find remainder by multiplying start and end // element, divided by middle element. // Replacing end element by remainder, Increment // start by 1 keeping end same as n-1. int remainder = (arr[start] * arr[end]) % copyArr[middle]; copyArr[end] = remainder; start++; } // If remainder is present in the array print “YES” // otherwise “NO”. int product = (arr[start] * arr[end]) / n; for ( int i = 0; i < n; i++) { if (copyArr[i] == product % n) { return true ; } } return false ; } public static void Main() { int [] arr = { 2, 3, 4, 8, 5, 7 }; int n = arr.Length; if (IsRemainderPresent(arr, n)) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } } |
Javascript
// JavaScript code for the above implementation function isRemainderPresent(arr, n) { let copyArr = [...arr]; // copying array elements let start = 0, end = n - 1; while (start < end - 1) { // Finding middle index as sum of start and end // divided by 2. let middle = Math.floor((start + end) / 2); // Find remainder by multiplying start and end // element, divided by middle element. // Replacing end element by remainder, Increment // start by 1 keeping end same as n-1. let remainder = (arr[start] * arr[end]) % copyArr[middle]; copyArr[end] = remainder; start++; } // If remainder is present in the array print “YES” // otherwise “NO”. let product = Math.floor((arr[start] * arr[end]) / n); for (let i = 0; i < n; i++) { if (copyArr[i] == product % n) { return true ; } } return false ; } let arr = [2, 3, 4, 8, 5, 7]; let n = arr.length; if (isRemainderPresent(arr, n)) { console.log( "YES" ); } else { console.log( "NO" ); } |
YES
Time Complexity: O(n)
Auxiliary Space: O(n)