Given an integer N, the task is to generate a sequence of N positive integers such that:
- Every element at the even position must be greater than the element succeeding it and the element preceding it i.e. arr[i – 1] < arr[i] > arr[i + 1]
- The sum of the elements must be even and the minimum possible (among all the possible sequences).
Examples:
Input: N = 4
Output: 1 2 1 2Input: N = 5
Output: 1 3 1 2 1
Approach: In order to get the sequence with the minimum sum possible, the sequence must be of form 1, 2, 1, 2, 1, 2, 1 … and for cases when the sum of the sequence is not even, any 2 from the sequence can be changed to a 3 to make the sum of the sequence even.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to print the required sequencevoid make_sequence(int N){ // arr[] will hold the sequence // sum variable will store the sum // of the sequence int arr[N + 1], sum = 0; for (int i = 1; i <= N; i++) { if (i % 2 == 1) arr[i] = 1; else arr[i] = 2; sum += arr[i]; } // If sum of the sequence is odd if (sum % 2 == 1) arr[2] = 3; // Print the sequence for (int i = 1; i <= N; i++) cout << arr[i] << " ";}// Driver Codeint main(){ int N = 9; make_sequence(N); return 0;} |
Java
// Java implementation of above approachclass GFG{// Function to print the required sequencestatic void make_sequence(int N){ // arr[] will hold the sequence // sum variable will store the sum // of the sequence int[] arr = new int[N + 1]; int sum = 0; for (int i = 1; i <= N; i++) { if (i % 2 == 1) arr[i] = 1; else arr[i] = 2; sum += arr[i]; } // If sum of the sequence is odd if (sum % 2 == 1) arr[2] = 3; // Print the sequence for (int i = 1; i <= N; i++) System.out.print(arr[i] + " ");}// Driver Codepublic static void main(String[] args){ int N = 9; make_sequence(N);}}// This code is contributed by iAyushRaj. |
Python 3
# Python 3 implementation of above approach# Function to print the required sequencedef make_sequence( N): # arr[] will hold the sequence # sum variable will store the sum # of the sequence arr = [0] * (N + 1) sum = 0 for i in range(1, N + 1): if (i % 2 == 1): arr[i] = 1 else: arr[i] = 2 sum += arr[i] # If sum of the sequence is odd if (sum % 2 == 1): arr[2] = 3 # Print the sequence for i in range(1, N + 1): print(arr[i], end = " ")# Driver Codeif __name__ == "__main__": N = 9 make_sequence(N)# This code is contributed by ita_c |
C#
// C# implementation of above approachusing System;class GFG{// Function to print the required sequencepublic static void make_sequence(int N){ // arr will hold the sequence // sum variable will store the sum // of the sequence int[] arr = new int[N + 1]; int sum = 0; for (int i = 1; i <= N; i++) { if (i % 2 == 1) arr[i] = 1; else arr[i] = 2; sum += arr[i]; } // If sum of the sequence is odd if (sum % 2 == 1) arr[2] = 3; // Print the sequence for (int i = 1; i <= N; i++) Console.Write(arr[i] + " ");}// Driver Codepublic static void Main(){ int N = 9; make_sequence(N);}}// This code is contributed by iAyushRaj. |
PHP
<?php// PHP implementation of above approach // Function to print the required sequence function make_sequence($N) { // arr[] will hold the sequence // sum variable will store the sum // of the sequence $arr = array(); $sum = 0; for ($i = 1; $i <= $N; $i++) { if ($i % 2 == 1) $arr[$i] = 1; else $arr[$i] = 2; $sum += $arr[$i]; } // If sum of the sequence is odd if ($sum % 2 == 1) $arr[2] = 3; // Print the sequence for ($i = 1; $i <= $N; $i++) echo $arr[$i], " "; } // Driver Code $N = 9; make_sequence($N); // This code is contributed by Ryuga?> |
Javascript
<script>// Javascript implementation of above approach// Function to print the required sequencefunction make_sequence(N){ // arr[] will hold the sequence // sum variable will store the sum // of the sequence var arr = Array(N+1), sum = 0; for (var i = 1; i <= N; i++) { if (i % 2 == 1) arr[i] = 1; else arr[i] = 2; sum += arr[i]; } // If sum of the sequence is odd if (sum % 2 == 1) arr[2] = 3; // Print the sequence for (var i = 1; i <= N; i++) document.write( arr[i] + " ");}// Driver Codevar N = 9;make_sequence(N);</script> |
Output:
1 3 1 2 1 2 1 2 1
Time Complexity: O(N)
Auxiliary Space: O(N), since N extra space has been taken.
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!
