Given a positive integer N, the task is to construct an array a[] using first N natural numbers which contains no such triplet (i, j, k) satisfying a[k] * 2 = a[i] + a[j] and i < j < k.
Examples:
Input: N = 3
Output: {2, 3, 1 }
Explanation:
Since no such triplet exists in the array satisfying the condition, the required output is { 2, 3, 1 }.Input: N = 10
Output: { 8, 4, 6, 10, 2, 7, 3, 5, 9, 1 }
Approach: The problem can be solved using Greedy technique. Follow the steps below to solve the problem:
- Recursively find the first (N / 2) elements of the resultant array and the last (N / 2) elements of the resultant array.
- Merge both halves of the array such that the first half of the array contains even numbers and the last half of the array contains the odd numbers.
- Finally, print the resultant array.
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to construct the array of size N// that contains no such triplet satisfying// the given conditionsvector<int> constructArray(int N){ // Base case if (N == 1) { return { 1 }; } // Stores the first half // of the array vector<int> first = constructArray(N / 2); // Stores the last half // of the array vector<int> last = constructArray(N - (N / 2)); // Stores the merged array vector<int> ans; // Insert even numbers for (auto e : first) { // Insert 2 * e ans.push_back(2 * e); } // Insert odd numbers for (auto o : last) { // Insert (2 * o - 1) ans.push_back((2 * o) - 1); } return ans;}// Function to print the resultant arrayvoid printArray(vector<int> ans, int N){ // Print resultant array cout << "{ "; for (int i = 0; i < N; i++) { // Print current element cout << ans[i]; // If i is not the last index // of the resultant array if (i != N - 1) { cout << ", "; } } cout << " }";}// Driver Codeint main(){ int N = 10; // Store the resultant array vector<int> ans = constructArray(N); printArray(ans, N); return 0;} |
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG{ // Function to construct the array of size N // that contains no such triplet satisfying // the given conditions static ArrayList<Integer> constructArray(int N) { // Base case if (N == 1) { ArrayList<Integer> a = new ArrayList<Integer>(1); a.add(1); return a; } // Stores the first half // of the array ArrayList<Integer> first = new ArrayList<Integer>(N); first = constructArray(N / 2); // Stores the last half // of the array ArrayList<Integer> last = new ArrayList<Integer>(N); last = constructArray(N - N / 2); ArrayList<Integer> ans = new ArrayList<Integer>(N); // Insert even numbers for(int i = 0; i < first.size(); i++) { // Insert 2 * first[i] ans.add(2 * first.get(i)); } // Insert odd numbers for(int i = 0; i < last.size(); i++) { // Insert (2 * last[i] - 1) ans.add(2 * last.get(i) - 1); } return ans;} // Driver code public static void main(String[] args) { int N = 10; ArrayList<Integer> answer = new ArrayList<Integer>(N); answer = constructArray(N); System.out.print("{"); for(int i = 0; i < answer.size(); i++) { System.out.print(answer.get(i)); System.out.print(", "); } System.out.print("}"); } } // This code is contributed by koulick_sadhu |
Python3
# Python3 program to implement# the above approach# Function to construct the array of size N# that contains no such triplet satisfying# the given conditionsdef constructArray(N) : # Base case if (N == 1) : a = [] a.append(1) return a; # Stores the first half # of the array first = constructArray(N // 2); # Stores the last half # of the array last = constructArray(N - (N // 2)); # Stores the merged array ans = []; # Insert even numbers for e in first : # Insert 2 * e ans.append(2 * e); # Insert odd numbers for o in last: # Insert (2 * o - 1) ans.append((2 * o) - 1); return ans;# Function to print the resultant arraydef printArray(ans, N) : # Print resultant array print("{ ", end = ""); for i in range(N) : # Print current element print(ans[i], end = ""); # If i is not the last index # of the resultant array if (i != N - 1) : print(", ",end = ""); print(" }", end = "");# Driver Codeif __name__ == "__main__" : N = 10; # Store the resultant array ans = constructArray(N); printArray(ans, N); # This code is contributed by AnkThon |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to construct the array of size N // that contains no such triplet satisfying // the given conditions static List<int> constructArray(int N) { // Base case if (N == 1) { List<int> a = new List<int>(1); a.Add(1); return a; } // Stores the first half // of the array List<int> first = new List<int>(); first = constructArray(N / 2); // Stores the last half // of the array List<int> last = new List<int>(); last = constructArray(N - N / 2); List<int> ans = new List<int>(); // Insert even numbers for(int i = 0; i < first.Count; i++) { // Insert 2 * first[i] ans.Add(2 * first[i]); } // Insert odd numbers for(int i = 0; i < last.Count; i++) { // Insert (2 * last[i] - 1) ans.Add(2 * last[i] - 1); } return ans;} // Driver code public static void Main() { int N = 10; List<int> answer = new List<int>(N); answer = constructArray(N); Console.Write("{"); for(int i = 0; i < answer.Count; i++) { Console.Write(answer[i]); Console.Write(", "); } Console.Write("}"); } }// This code is contributed by sanjoy_62 |
Javascript
<script> // JavaScript program to implement the above approach // Function to construct the array of size N // that contains no such triplet satisfying // the given conditions function constructArray(N) { // Base case if (N == 1) { let a = []; a.push(1); return a; } // Stores the first half // of the array let first = []; first = constructArray(parseInt(N / 2, 10)); // Stores the last half // of the array let last = []; last = constructArray(N - parseInt(N / 2, 10)); let ans = []; // Insert even numbers for(let i = 0; i < first.length; i++) { // Insert 2 * first[i] ans.push(2 * first[i]); } // Insert odd numbers for(let i = 0; i < last.length; i++) { // Insert (2 * last[i] - 1) ans.push(2 * last[i] - 1); } return ans; } let N = 10; let answer = []; answer = constructArray(N); document.write("{"); for(let i = 0; i < answer.length; i++) { document.write(answer[i]); document.write(", "); } document.write("}");</script> |
Output:
{ 8, 4, 6, 10, 2, 7, 3, 5, 9, 1 }
Time Complexity : O(N * log(N))
Auxiliary Space: O(N)
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!
