Maximum sum of Bitwise XOR of elements with their respective positions in a permutation of size N
Given a positive integer N, the task for any permutation of size N having elements over the range [0, N – 1], is to calculate the sum of Bitwise XOR of all elements with their respective position.
For Example: For the permutation {3, 4, 2, 1, 0}, sum = (0^3 + 1^4 + 2^2 + 3^1 + 4^0) = 2.
Examples:
Input: N = 3
Output: 6
Explanation: For the permutations {1, 2, 0} and {2, 0, 1}, the sum is 6.Input: N = 2
Output: 2
Approach: To solve this problem, the idea is to recursion to generate all possible permutations of the integers [0, N – 1] and calculate the score for each one of them and then find the maximum score among all the permutations formed.
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 the scoreint calcScr(vector<int>arr){ // Stores the possible score for // the current permutation int ans = 0; // Traverse the permutation array for(int i = 0; i < arr.size(); i++) ans += (i ^ arr[i]); // Return the final score return ans;}// Function to generate all the possible// permutation and get the max scoreint getMax(vector<int> arr, int ans, vector<bool> chosen, int N){ // If arr[] length is equal to N // process the permutation if (arr.size() == N){ ans = max(ans, calcScr(arr)); return ans; } // Generating the permutations for (int i = 0; i < N; i++) { // If the current element is // chosen if(chosen[i]) continue; // Mark the current element // as true chosen[i] = true; arr.push_back(i); // Recursively call for next // possible permutation ans = getMax(arr, ans, chosen, N); // Backtracking chosen[i] = false; arr.pop_back(); } // Return the ans return ans;}// Driver Codeint main(){ int N = 2; // Stores the permutation vector<int> arr; // To display the result int ans = -1; vector<bool>chosen(N,false); ans = getMax(arr, ans, chosen, N); cout << ans << endl;}// This code is contributed by bgangwar59. |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to calculate the scorestatic int calcScr(ArrayList<Integer>arr){ // Stores the possible score for // the current permutation int ans = 0; // Traverse the permutation array for(int i = 0; i < arr.size(); i++) ans += (i ^ arr.get(i)); // Return the final score return ans;}// Function to generate all the possible// permutation and get the max scorestatic int getMax(ArrayList<Integer> arr, int ans, ArrayList<Boolean> chosen, int N){ // If arr[] length is equal to N // process the permutation if (arr.size() == N) { ans = Math.max(ans, calcScr(arr)); return ans; } // Generating the permutations for (int i = 0; i < N; i++) { // If the current element is // chosen if(chosen.get(i)) continue; // Mark the current element // as true chosen.set(i, true); arr.add(i); // Recursively call for next // possible permutation ans = getMax(arr, ans, chosen, N); // Backtracking chosen.set(i, false); arr.remove(arr.size()-1); } // Return the ans return ans;}// Driver Codepublic static void main(String[] args){ int N = 2; // Stores the permutation ArrayList<Integer> arr = new ArrayList<Integer>(); // To display the result int ans = -1; ArrayList<Boolean> chosen = new ArrayList<Boolean>(Collections.nCopies(N, false)); ans = getMax(arr, ans, chosen, N); System.out.print(ans +"\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Function to generate all the possible# permutation and get the max scoredef getMax(arr, ans, chosen, N): # If arr[] length is equal to N # process the permutation if len(arr) == N: ans = max(ans, calcScr(arr)) return ans # Generating the permutations for i in range(N): # If the current element is # chosen if chosen[i]: continue # Mark the current element # as true chosen[i] = True arr.append(i) # Recursively call for next # possible permutation ans = getMax(arr, ans, chosen, N) # Backtracking chosen[i] = False arr.pop() # Return the ans return ans# Function to calculate the scoredef calcScr(arr): # Stores the possible score for # the current permutation ans = 0 # Traverse the permutation array for i in range(len(arr)): ans += (i ^ arr[i]) # Return the final score return ans# Driver CodeN = 2# Stores the permutationarr = []# To display the resultans = -1chosen = [False for i in range(N)]ans = getMax(arr, ans, chosen, N)print(ans) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to calculate the score static int calcScr(List<int>arr) { // Stores the possible score for // the current permutation int ans = 0; // Traverse the permutation array for(int i = 0; i < arr.Count; i++) ans += (i ^ arr[i]); // Return the readonly score return ans; } // Function to generate all the possible // permutation and get the max score static int getMax(List<int> arr, int ans, List<Boolean> chosen, int N) { // If []arr length is equal to N // process the permutation if (arr.Count == N) { ans = Math.Max(ans, calcScr(arr)); return ans; } // Generating the permutations for (int i = 0; i < N; i++) { // If the current element is // chosen if(chosen[i]) continue; // Mark the current element // as true chosen[i] = true; arr.Add(i); // Recursively call for next // possible permutation ans = getMax(arr, ans, chosen, N); // Backtracking chosen[i] = false; arr.Remove(arr.Count-1); } // Return the ans return ans; } // Driver Code public static void Main(String[] args) { int N = 2; // Stores the permutation List<int> arr = new List<int>(); // To display the result int ans = -1; List<bool> chosen = new List<bool>(N); for(int i = 0; i < N; i++) chosen.Add(false); ans = getMax(arr, ans, chosen, N); Console.Write(ans +"\n"); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program for the above approach// Function to calculate the scorefunction calcScr(arr) { // Stores the possible score for // the current permutation let ans = 0; // Traverse the permutation array for (let i = 0; i < arr.length; i++) ans += (i ^ arr[i]); // Return the final score return ans;}// Function to generate all the possible// permutation and get the max scorefunction getMax(arr, ans, chosen, N) { // If arr[] length is equal to N // process the permutation if (arr.length == N) { ans = Math.max(ans, calcScr(arr)); return ans; } // Generating the permutations for (let i = 0; i < N; i++) { // If the current element is // chosen if (chosen[i]) continue; // Mark the current element // as true chosen[i] = true; arr.push(i); // Recursively call for next // possible permutation ans = getMax(arr, ans, chosen, N); // Backtracking chosen[i] = false; arr.pop(); } // Return the ans return ans;}// Driver Codelet N = 2;// Stores the permutationlet arr = [];// To display the resultlet ans = -1;let chosen = new Array(N).fill(false);ans = getMax(arr, ans, chosen, N);document.write(ans + "<br>");// This code is contributed by gfgking</script> |
Output:
2
Time Complexity: O(N*N!)
Auxiliary Space: O(N)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
