Horje
Create Array of distinct elements where odd indexed elements are multiple of left neighbour

Given an integer N, the task is to generate an array A[] of length N such that it satisfies the following conditions for all 1 ? i ? N?1:

  • Ai is multiple of Ai-1 when i is odd
  • Ai is not multiple of Ai-1 when i is even
  • All Ai are pairwise distinct
  • 1 ? Ai ? 2?N

Note: If there are multiple answers print any of them.

    Examples:

Input: N = 4
Output: 3 6 4 8 
?Explanation:  [3, 6, 4, 8] is a valid array because:
A1 = 3 is multiple of A2 = 6
A2 = 6 is not multiple of A3 = 4
A3 = 4 is multiple of A4 = 8.

Input: N = 6
Output: 4 8 5 10 6 12

Approach: The problem can be solved based on the following observation:

Observations:

Let x = N ? ?N / 2? + 1. Then, the following sequence is valid: [x, 2?x, x + 1, 2?(x + 1), x + 2, …]

  • It is easy to see that the elements at odd indices are in increasing order from x?N. Similarly, the elements at even indices are in increasing order from 2?x?2?N (from 2?x?2?(N ? 1) when N is odd).
  • Then, 2?x = 2?(N ? ?N / 2? + 1) > N implies the sets {x, x + 1, …, N} and {2?x, 2?(x + 1), …, 2?N} are disjoint. Therefore, all elements of the above sequence are unique.
  • Ai is multiple of Ai-1 can be trivially verified to be true for all odd
    Ai is not multiple of Ai-1 holds true for all even i.

Thus, the provided sequence fulfills all requirements of the problem, and is therefore valid!

Follow the below steps to solve the problem:

  • Initialize a variable oddElement = (N / 2) + 1 for odd indexed elements.
  • Initialize a variable evenElement = oddElement * 2 for even indexed elements.
  • Traverse a loop from 1 till N on i:
    • If i is odd print oddElement.
      • Assign evenElement = oddElement * 2.
      • Increment the evenElement.   
    • Else print the evenElement.
       

Below is the implementation of the above approach.

C++

#include <iostream>
using namespace std;
#include <cmath>
 
// Function to find array
void find(int N)
{
    int oddElement = N - (int)floor(N / 2) + 1;
    int evenElement = 2 * oddElement;
 
    for (int i = 1; i <= N; i++) {
 
        // For odd indices
        if ((i % 2) != 0) {
            cout << oddElement << " ";
            evenElement = 2 * oddElement;
            oddElement++;
        }
 
        // For even indices
        else {
            cout << evenElement << " ";
        }
    }
}
 
// Driver Code
int main()
{
    int N = 4;
   
    // Function call
    find(N);
}
 
// This code is contributed by aarohirai2616.

Java

// Java code to implement the approach
 
import java.io.*;
import java.util.*;
 
public class GFG {
 
    // Function to find array
    public static void find(int N)
    {
        int oddElement = N - (int)Math.floor(N / 2) + 1;
        int evenElement = 2 * oddElement;
 
        for (int i = 1; i <= N; i++) {
 
            // For odd indices
            if ((i % 2) != 0) {
                System.out.print(oddElement + " ");
                evenElement = 2 * oddElement;
                oddElement++;
            }
 
            // For even indices
            else {
                System.out.print(evenElement + " ");
            }
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 4;
 
        // Function call
        find(N);
    }
}

Python3

# Python code to implement the approach
import math
 
# Function to find array
def find(N):
    oddElement = int(N - (N/2) + 1)
    evenElement = 2 * oddElement
 
    for i in range(1, N + 1):
       
        # For odd indices
        if((i % 2) is not 0):
            print(oddElement, end=" ")
            evenElement = 2 * oddElement
            oddElement += 1
 
        # For even indices
        else:
            print(evenElement, end=" ")
 
N = 4
 
# Function call
find(N)
 
# This code is contributed by lokeshmvs21.

C#

// C# code to implement the approach
using System;
class GFG {
 
 
  // Function to find array
  public static void find(int N)
  {
    int oddElement = N - N / 2 + 1;
    int evenElement = 2 * oddElement;
 
    for (int i = 1; i <= N; i++) {
 
      // For odd indices
      if ((i % 2) != 0) {
        Console.Write(oddElement + " ");
        evenElement = 2 * oddElement;
        oddElement++;
      }
 
      // For even indices
      else {
        Console.Write(evenElement + " ");
      }
    }
  }
 
 
  // Driver code
  public static void Main(string[] args)
  {
    int N = 4;
 
    // Function call
    find(N);
  }
}
 
// This code is contributed by code_hunt.

Javascript

// Javascript  code to implement the approach
 
// Function to find array
function find(N){
 
    let oddElement = N - Math.floor(N / 2) + 1;
    let evenElement = 2 * oddElement;
 
    for(let i = 1; i <= N; i++) {
 
        // For odd indices
        if ((i % 2) != 0){
            process.stdout.write(oddElement + " ");
            evenElement = 2 * oddElement;
            oddElement++;
          }
           
        // For even indices
        else{
           process.stdout.write(evenElement + " ");
        }
    }
}
 
 // Driver Code
 let N = 4;
 
    // Function Call
 find(N);
  
 // This code is contributed by aarohirai2616.

Output

3 6 4 8

Time Complexity: O(N)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Maximum prefix sum which is equal to suffix sum such that prefix and suffix do not overlap Maximum prefix sum which is equal to suffix sum such that prefix and suffix do not overlap
Minimum time to fulfil all orders Minimum time to fulfil all orders
Find the Array element left after alternate removal of minimum and maximum Find the Array element left after alternate removal of minimum and maximum
Minimize division by 2 to make Array of alternate odd and even elements Minimize division by 2 to make Array of alternate odd and even elements
Next Permutation Next Permutation

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje