Given an array arr[] of length N and an integer M, the task is to determine if a strictly increasing sequence can be formed by merging three consecutive elements exactly M times.
Note: Merging three elements means removing all three of them and inserting a single element having value same as the sum of the three at the same position.
Examples:
Input: arr = {10, 24, 26, 2, 32, 36}, M = 2
Output: True
Explanation: 1st Operation – Merge arr[3], arr[4] and arr[5] to get arr[4] = 70,
Delete arr[5] and arr[6], arr = {10, 24, 26, 70}
2nd Operation – Merge arr[0], arr[1] and arr[2] to get arr[0] = 60
Delete arr[1] and arr[2], arr = {60, 70}, which is a strictly increasing array.Input: arr = {1, 2, 3}, M = 2
Output: False
Explanation: 1st Operation – Merge arr[0], arr[1] and arr[2] to get arr[0] = 6,
Delete arr[1] and arr[2], arr = {6}
2nd Operation is not possible as there are not enough elements left.
Approach:
This problem can be solved using greedy approach. Each time decreasing sequence is found, merge the following three elements in order to make the array increasing, remove two elements and decrease the array size. Keep on repeating this process to find whether array can be transformed into strictly increasing after all the M operations.
Follow the below steps to solve the given problem:
- Traverse until i>0 and M>0 and the array is not empty.
- For each position there are three choices:
- If the arr[i]<arr[i-1] and i+2<arr.size() then perform arr[i]=arr[i]+arr[i+1]+arr[i+2] and delete arr[i+1] and arr[i+2] and call the function recursively with new array and M-1.
- If the arr[i]<arr[i-1] and i>=2 then perform arr[i-2]=arr[i-2]+arr[i]+arr[i-1] and delete arr[i-1] and arr[i] and call the function recursively with new array and M-1.
- If the arr[i]<arr[i-1] and i<2 then perform arr[i-1]=arr[i-1]+arr[i]+arr[i+1] and delete arr[i] and arr[i+1] and call the function recursively with new array and M-1.
- If the array is strictly increasing and 2*M<size of array arr then return True else return False.
Below is the implementation of this approach:
C++14
// C++ code to implement the greedy approach#include <bits/stdc++.h>using namespace std;// function to check whether array is strictly increasing or notbool isIncreasing(vector<int>& arr){ for (int i = 1; i < arr.size(); i++) { if (arr[i - 1] > arr[i]) return false; } return true;}// function to check whether we can make// given an array an increasing array// in exact M operationsbool make_inc_seq(vector<int> arr, int M){ vector<int> temp(arr); if (isIncreasing(arr) && 2 * M < arr.size()) return 1; else if (!M || arr.size() < 3) return 0; bool ans1 = 0, ans2 = 0, ans3 = 0; for (int i = arr.size() - 1; i > 0; i--) { if (arr[i] < arr[i - 1]) { if (arr.size() > i + 2 && i >= 0) { arr.clear(); arr = temp; arr[i] = arr[i] + arr[i + 1] + arr[i + 2]; arr.erase(arr.begin() + i + 1); arr.erase(arr.begin() + i + 1); ans1 = make_inc_seq(arr, M - 1); } if (i >= 2 && i < arr.size()) { arr.clear(); arr = temp; arr[i - 2] = arr[i - 2] + arr[i - 1] + arr[i]; arr.erase(arr.begin() + i); arr.erase(arr.begin() + i - 1); ans2 = make_inc_seq(arr, M - 1); } if (i >= 1 && i + 1 < arr.size()) { arr.clear(); arr = temp; arr[i - 1] = arr[i - 1] + arr[i] + arr[i + 1]; arr.erase(arr.begin() + i); arr.erase(arr.begin() + i); ans3 = make_inc_seq(arr, M - 1); } } } return ans1 || ans2 || ans3;}// Driver's codeint main(){ vector<int> arr = { 10, 24, 26, 2, 32, 36 }; int M = 2; if (make_inc_seq(arr, M)) cout << "True"; else cout << "False"; return 0;}// this code is contributed by prophet1999 |
Java
// Java code to implement the greedy approachimport java.util.*;public class GFG { // function to check whether array is strictly // increasing or not public static boolean isIncreasing(List<Integer> arr) { for (int i = 1; i < arr.size(); i++) { if (arr.get(i - 1) > arr.get(i)) return false; } return true; } // function to check whether we can make // given an array an increasing array // in exact M operations public static boolean makeIncSeq(List<Integer> arr, int M) { List<Integer> temp = new ArrayList<>(arr); if (isIncreasing(arr) && 2 * M < arr.size()) return true; else if (M == 0 || arr.size() < 3) return false; boolean ans1 = false, ans2 = false, ans3 = false; for (int i = arr.size() - 1; i > 0; i--) { if (arr.get(i) < arr.get(i - 1)) { if (arr.size() > i + 2 && i >= 0) { arr = new ArrayList<>(temp); arr.set(i, arr.get(i) + arr.get(i + 1) + arr.get(i + 2)); arr.remove(i + 1); arr.remove(i + 1); ans1 = makeIncSeq(arr, M - 1); } if (i >= 2 && i < arr.size()) { arr = new ArrayList<>(temp); arr.set(i - 2, arr.get(i - 2) + arr.get(i - 1) + arr.get(i)); arr.remove(i); arr.remove(i - 1); ans2 = makeIncSeq(arr, M - 1); } if (i >= 1 && i + 1 < arr.size()) { arr = new ArrayList<>(temp); arr.set(i - 1, arr.get(i - 1) + arr.get(i) + arr.get(i + 1)); arr.remove(i); arr.remove(i); ans3 = makeIncSeq(arr, M - 1); } } } return ans1 || ans2 || ans3; } // Driver's code public static void main(String[] args) { List<Integer> a// Java code to implement the greedy approachimport java.util.*;public class GFG { // function to check whether array is strictly // increasing or not public static boolean isIncreasing(List<Integer> arr) { for (int i = 1; i < arr.size(); i++) { if (arr.get(i - 1) > arr.get(i)) return false; } return true; } // function to check whether we can make // given an array an increasing array // in exact M operations public static boolean makeIncSeq(List<Integer> arr, int M) { List<Integer> temp = new ArrayList<>(arr); if (isIncreasing(arr) && 2 * M < arr.size()) return true; else if (M == 0 || arr.size() < 3) return false; boolean ans1 = false, ans2 = false, ans3 = false; for (int i = arr.size() - 1; i > 0; i--) { if (arr.get(i) < arr.get(i - 1)) { if (arr.size() > i + 2 && i >= 0) { arr = new ArrayList<>(temp); arr.set(i, arr.get(i) + arr.get(i + 1) + arr.get(i + 2)); arr.remove(i + 1); arr.remove(i + 1); ans1 = makeIncSeq(arr, M - 1); } if (i >= 2 && i < arr.size()) { arr = new ArrayList<>(temp); arr.set(i - 2, arr.get(i - 2) + arr.get(i - 1) + arr.get(i)); arr.remove(i); arr.remove(i - 1); ans2 = makeIncSeq(arr, M - 1); } if (i >= 1 && i + 1 < arr.size()) { arr = new ArrayList<>(temp); arr.set(i - 1, arr.get(i - 1) + arr.get(i) + arr.get(i + 1)); arr.remove(i); arr.remove(i); ans3 = makeIncSeq(arr, M - 1); } } } return ans1 || ans2 || ans3; } // Driver's code public static void main(String[] args) { List<Integer> arr = new ArrayList<>( Arrays.asList(10, 24, 26, 2, 32, 36)); int M = 2; if (makeIncSeq(arr, M)) System.out.println("True"); else System.out.println("False"); }}rr = new ArrayList<>( Arrays.asList(10, 24, 26, 2, 32, 36)); int M = 2; if (makeIncSeq(arr, M)) System.out.println("True"); else System.out.println("False"); }} |
Python3
# function to check whether array is strictly increasing or notdef isIncreasing(arr): for i in range(1, len(arr)): if arr[i - 1] > arr[i]: return False return True# function to check whether we can make# given an array an increasing array# in exact M operationsdef make_inc_seq(arr, M): temp = arr.copy() if isIncreasing(arr) and 2 * M < len(arr): return True elif M == 0 or len(arr) < 3: return False ans1, ans2, ans3 = False, False, False for i in range(len(arr) - 1, 0, -1): if arr[i] < arr[i - 1]: if len(arr) > i + 2 and i >= 0: arr = temp.copy() arr[i] += arr[i + 1] + arr[i + 2] arr.pop(i + 1) arr.pop(i + 1) ans1 = make_inc_seq(arr, M - 1) if i >= 2 and i < len(arr): arr = temp.copy() arr[i - 2] += arr[i - 1] + arr[i] arr.pop(i) arr.pop(i - 1) ans2 = make_inc_seq(arr, M - 1) if i >= 1 and i + 1 < len(arr): arr = temp.copy() arr[i - 1] += arr[i] + arr[i + 1] arr.pop(i) arr.pop(i) ans3 = make_inc_seq(arr, M - 1) return ans1 or ans2 or ans3# Driver's codearr = [10, 24, 26, 2, 32, 36]M = 2if make_inc_seq(arr, M): print("True")else: print("False") |
C#
// C# code to implement the greedy approachusing System;using System.Collections.Generic;public class Solution{ // function to check whether array is strictly increasing or not public static bool IsIncreasing(List<int> arr) { for (int i = 1; i < arr.Count; i++) { if (arr[i - 1] > arr[i]) { return false; } } return true; } // function to check whether we can make // given an array an increasing array // in exact M operations public static bool MakeIncSeq(List<int> arr, int M) { List<int> temp = new List<int>(arr); if (IsIncreasing(arr) && 2 * M < arr.Count) { return true; } else if (M == 0 || arr.Count < 3) { return false; } bool ans1 = false, ans2 = false, ans3 = false; for (int i = arr.Count - 1; i > 0; i--) { if (arr[i] < arr[i - 1]) { if (arr.Count > i + 2 && i >= 0) { arr = new List<int>(temp); arr[i] = arr[i] + arr[i + 1] + arr[i + 2]; arr.RemoveAt(i + 1); arr.RemoveAt(i + 1); ans1 = MakeIncSeq(arr, M - 1); } if (i >= 2 && i < arr.Count) { arr = new List<int>(temp); arr[i - 2] = arr[i - 2] + arr[i - 1] + arr[i]; arr.RemoveAt(i); arr.RemoveAt(i - 1); ans2 = MakeIncSeq(arr, M - 1); } if (i >= 1 && i + 1 < arr.Count) { arr = new List<int>(temp); arr[i - 1] = arr[i - 1] + arr[i] + arr[i + 1]; arr.RemoveAt(i); arr.RemoveAt(i); ans3 = MakeIncSeq(arr, M - 1); } } } return ans1 || ans2 || ans3; } // Driver's code public static void Main() { List<int> arr = new List<int> { 10, 24, 26, 2, 32, 36 }; int M = 2; if (MakeIncSeq(arr, M)) { Console.WriteLine("True"); } else { Console.WriteLine("False"); } }} |
Javascript
// Javascript code to implement the greedy approach// Function to check whether array is strictly increasing or notfunction isIncreasing(arr){ for (let i = 1; i < arr.length; i++) { if (arr[i - 1] > arr[i]) return false; } return true;}// function to check whether we can make// given an array an increasing array// in exact M operationsfunction make_inc_seq(arr, M){ let temp = arr.slice(); if (isIncreasing(arr) == true && 2 * M < arr.length) return 1; else if (!M || arr.length < 3) return 0; let ans1 = 0, ans2 = 0, ans3 = 0; for (let i = arr.length - 1; i > 0; i--) { if (arr[i] < arr[i - 1]) { if (arr.length > i + 2 && i >= 0) { arr.splice(0, arr.length); arr = temp.slice(); arr[i] = arr[i] + arr[i + 1] + arr[i + 2]; arr.splice(i + 1, 1); arr.splice(i + 1, 1); ans1 = make_inc_seq(arr, M - 1); } if (i >= 2 && i < arr.length) { arr.splice(0, arr.length); arr = temp.slice(); arr[i - 2] = arr[i - 2] + arr[i - 1] + arr[i]; arr.splice(i, 1); arr.splice(i - 1, 1); ans2 = make_inc_seq(arr, M - 1); } if (i >= 1 && i + 1 < arr.length) { arr.splice(0, arr.length); arr = temp.slice(); arr[i - 1] = arr[i - 1] + arr[i] + arr[i + 1]; arr.splice(i, 1); arr.splice(i, 1); ans3 = make_inc_seq(arr, M - 1); } } } return ans1 || ans2 || ans3;}// Driver's codelet arr = [ 10, 24, 26, 2, 32, 36 ];let M = 2;if (make_inc_seq(arr, M)) console.log("True");else console.log("False");// This code is contributed by Nidhi goel. |
Output
True
Time Complexity: O(3min(M, N)*N)
Auxiliary Space: O(N)
Share your thoughts in the comments
