Construct an array of first N natural numbers having no triplet (i, j, k) such that a[i] + a[j] = 2* a[k] where i < j< k

0 0 5 minutes read

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 conditions
vector<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 array
void 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 Code
int 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 conditions
def 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 array
def 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 Code
if __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 zambiatek!