Given a positive integer N, the task is to find a permutation of length N having Bitwise OR of any of its subarray greater than or equal to the length of the subarray.
Examples:
Input: N = 5
Output: 1 3 5 2 4
Explanation:
Consider the subarray {1, 3, 5} from the permutation {1, 3, 5, 2, $}.
Length of the subarray = 3
Bitwise OR of the subarray = 1 | 3 | 5 = 7 ( which is greater than 3)
Similarly, every subarray of any length smaller than equal to N will satisfy the condition.Input: 4
Output: 4 3 1 2
Approach: Actually any permutation of length N satisfies the required conditions based on the following facts:
- Bitwise OR of any set of numbers is greater than or equal to the maximum number present in that set.
- Since any subarray will contain at least one element greater than or equal to its length, any permutation satisfies the given condition.
Below is the implementation of the above approach:
C++
// C++ implementation of// the above approach#include <iostream>using namespace std;// Function to print the// required permutationvoid findPermutation(int N){ for(int i = 1; i <= N; i++) cout << i << " "; cout << endl;}// Driver codeint main() { int N = 5; findPermutation(N); return 0;} |
Java
// Java implementation of// the above approachimport java.util.*;class GFG{ // Function to print the// required permutationstatic void findPermutation(int N){ for(int i = 1; i <= N; i++) System.out.print(i + " ");} // Driver Codepublic static void main(String[] args){ int N = 5; findPermutation(N);}}// This code is contributed by susmitakundugoaldanga |
Python3
# Python3 implementation of# the above approach# Function to print the# required permutationdef findPermutation(N): for i in range(1, N + 1, 1): print(i, end= " ") print("\n", end = "")# Driver codeif __name__ == '__main__': N = 5 findPermutation(N) # This code is contributed by ipg2016107. |
C#
// C# implementation of// the above approachusing System;class GFG{ // Function to print the// required permutationstatic void findPermutation(int N){ for(int i = 1; i <= N; i++) Console.Write(i + " ");}// Driver codepublic static void Main() { int N = 5; findPermutation(N);}}// This code is contributed by SURENDRA_GANGWAR |
Javascript
<script>// javascript implementation of// the above approach// Function to print the// required permutationfunction findPermutation(N){ for(var i = 1; i <= N; i++) document.write( i + " "); document.write("<br>");}var N = 5;findPermutation(N);//This code in contributed by SoumikMondal</script> |
Output:
1 2 3 4 5
Time Complexity : O(N)
Auxiliary Space: O(1)
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!
Share your thoughts in the comments