Given an integer N., The task is to find the number of distinct permutations of length N, such that the bitwise AND value of each permutation is zero.
Examples:
Input: N = 1
Output: 0
Explanation: There is only one permutation of length 1: [1] and it’s bitwise AND is 1 .
Input: N = 3
Output: 6
Explanation: Permutations of length N having bitwise AND as 0 are : [1, 2, 3], [1, 3, 2], [2, 1, 3], [3, 1, 2], [2, 3, 1], [3, 2, 1] .
Approach: The task can be solved using observations. One can observe that if a number is a power of 2, let’s say ‘x‘, bitwise AND of x & (x-1) is always zero. All permutations of length greater than 1, have bitwise AND as zero, and for N = 1, the count of distinct permutations is 0. Therefore, the required count is equal to the number of possible permutations i.e N!
Below is the implementation of the above approach –
C++
// C++ program for the// above approach#include <bits/stdc++.h>using namespace std;// Function to calculate factorial// of a numberlong long int fact(long long N){ long long int ans = 1; for (int i = 2; i <= N; i++) ans *= i; return ans;}// Function to find distinct no of// permutations having bitwise and (&)// equals to 0long long permutation_count(long long n){ // corner case if (n == 1) return 0; return fact(n);}// Driver codeint main(){ long long N = 3; cout << permutation_count(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to calculate factorial// of a numberstatic long fact( long N){ long ans = 1; for (int i = 2; i <= N; i++) ans *= i; return ans;}// Function to find distinct no of// permutations having bitwise and (&)// equals to 0static long permutation_count(long n){ // corner case if (n == 1) return 0; return fact(n);} public static void main (String[] args) { long N = 3; System.out.println(permutation_count(N)); }}// This code is contributed by Potta Lokesh |
Python3
# Python 3 program for the# above approach# Function to calculate factorial# of a numberdef fact(N): ans = 1 for i in range(2, N + 1): ans *= i return ans# Function to find distinct no of# permutations having bitwise and (&)# equals to 0def permutation_count(n): # corner case if (n == 1): return 0 return fact(n)# Driver codeif __name__ == "__main__": N = 3 print(permutation_count(N)) # This code is contributed by ukasp. |
C#
// C# program for the// above approachusing System;class GFG{// Function to calculate factorial// of a numberstatic long fact(long N){ long ans = 1; for (int i = 2; i <= N; i++) ans *= i; return ans;}// Function to find distinct no of// permutations having bitwise and (&)// equals to 0static long permutation_count(long n){ // corner case if (n == 1) return 0; return fact(n);}// Driver codepublic static void Main(){ long N = 3; Console.Write(permutation_count(N));}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript program for the// above approach// Function to calculate factorial// of a numberfunction fact(N){ let ans = 1; for (let i = 2; i <= N; i++) ans *= i; return ans;}// Function to find distinct no of// permutations having bitwise and (&)// equals to 0function permutation_count(n){ // corner case if (n == 1) return 0; return fact(n);}// Driver codelet N = 3;document.write(permutation_count(N));// This code is contributed by Samim Hossain Mondal.</script> |
6
Time complexity: O(N)
Auxiliary Space: O(1)
