Non-Repeating Bitwise OR Permutation
Given an integer N (N >= 3). Then the task is to output a permutation such that the bitwise OR of the previous two elements is not equal to the current element, given that the previous two element exists.
Note: If multiple permutation exists, just print any valid permutation.
Examples:
Input: N = 3
Output: 1 3 2
Explanation:
- First element: A[1] = 1. Two previous elements don’t exist. Therefore, no need to check.
- Second element: A[2] = 3. Two previous elements don’t exist. Therefore, no need to check.
- Third element: A[3] = 2. Two previous elements are 1 and 3. Bitwise OR of 1 and 3 is (1 | 3) = 3, which is not equal to 2.
Thus, permutation satisfies the problem constraints.
Input: N = 5
Output: 2 1 5 3 4
Explanation:
- First element: A[1] = 2. Two previous elements don’t exist. Therefore, no need to check.
- Second element: A[2] = 1. Two previous elements don’t exist. Therefore, no need to check.
- Third element: A[3] = 5. Two previous elements are 1 and 2. Bitwise OR of 1 and 2 is (1 | 2) = 3, which is not equal to 5.
- Fourth element: A[4] = 3. Two previous elements are 1 and 5. Bitwise OR of 1 and 5 is (1 | 5) = 5, which is not equal to 3.
- Fifth element: A[5] = 4. Two previous elements are 5 and 3. Bitwise OR of 5 and 3 is (5 | 3) = 7, which is not equal to 4.
Approach: Implement the idea below to solve the problem
The problem is observation based. It must be noted that if X, Y, Z are positive integers such that Z = (X | Y), Then Z >= max(X, Y). Therefore, If we output N numbers in decreasing order then there’s no way our permutation can be wrong. Hence, it’s our required answer.
Steps taken to solve the problem:
- Run a loop reversely from i = N to i = 1 and output i.
Code to implement the approach:
C++
#include <iostream> using namespace std; void PrintPermutation( int N) { for ( int i = N; i >= 1; i--) { cout << i << " " ; } } int main() { // Input int N = 5; // Function call PrintPermutation(N); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { public static void main(String[] args) { // Input int N = 5 ; // Function call Print_permutation(N); } public static void Print_permutation( int N) { for ( int i = N; i >= 1 ; i--) { System.out.print(i + " "); } } } |
Python3
# Python program for the above approach def print_permutation(N): for i in range (N, 0 , - 1 ): print (i, end = " " ) # Input N = 5 # Function call print_permutation(N) # This code is contributed by Susobhan Akhuli |
C#
using System; public class GFG { public static void Main( string [] args) { // Input int N = 5; // Function call PrintPermutation(N); } public static void PrintPermutation( int N) { for ( int i = N; i >= 1; i--) { Console.Write(i + " " ); } } } |
Javascript
<script> // Javascript program for the above approach // Function to print permutation function printPermutation(N) { for (let i = N; i >= 1; i--) { document.write(i + " " ); } } // Input const N = 5; // Function call printPermutation(N); // This code is contributed by Susobhan Akhuli </script> |
5 4 3 2 1
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us