Find an N-length permutation that contains subarrays with sum less than Bitwise XOR
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 permutation void findPermutation( int N) { for ( int i = 1; i <= N; i++) cout << i << " " ; cout << endl; } // Driver code int main() { int N = 5; findPermutation(N); return 0; } |
Java
// Java implementation of // the above approach import java.util.*; class GFG{ // Function to print the // required permutation static void findPermutation( int N) { for ( int i = 1 ; i <= N; i++) System.out.print(i + " " ); } // Driver Code public 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 permutation def findPermutation(N): for i in range ( 1 , N + 1 , 1 ): print (i, end = " " ) print ( "\n" , end = "") # Driver code if __name__ = = '__main__' : N = 5 findPermutation(N) # This code is contributed by ipg2016107. |
C#
// C# implementation of // the above approach using System; class GFG{ // Function to print the // required permutation static void findPermutation( int N) { for ( int i = 1; i <= N; i++) Console.Write(i + " " ); } // Driver code public 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 permutation function 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)