Given an array arr[] of size N ( N is even ), the task is to construct an array B[] such that the sum of B[i] XOR PrefixXor[i], where 1 ? i ? N is even and is divisible by the first N/2 elements of arr[].
PrefixXor[] array is an array where each element will indicate the XOR of all elements from 1st element to the current index element.
Examples:
Input: N = 4, arr[] = {2, 6, 1, 5}
Output: B[] = {0, 6, 3, 6}
Explanation: Since, prefix array is prefixXor[] = {2, 4, 5, 0}, (2 ^ 0) + (4 ^ 6) + (5 ^ 3) + (0^6) = 2 + 2 + 6 + 6 = 16, which is even and divisible by 8.Input: N = 6, arr[] = {2, 5, 3, 4, 6, 1}
Output: B[] = {0, 5, 1, 5, 5, 4}
Explanation: Since prefix, the array is prefixXor[]={2, 7, 4, 0, 6, 7}, So, (2 ^ 0) + (7 ^ 5) + (4 ^ 1) + (0 ^ 5) + (6 ^ 5) + (7 ^ 4) = 2 + 2 + 5 + 5 + 3 + 3 = 20, which is even and divisible by 10.
Approach: Implement the idea below to solve the problem:
Let’s first analyze the question. The given sum should be even and should be divisible by the first N/2 elements. So more formally it means :
if array arr[] = {a, b, c, d}, then its prefix xor is Prefix_xor[]=[a, a^b, a^b^c, a^b^c^d}
Let assume array B[] = {x, y, z, w} then S= (x^a) + (y^(a^b)) + (z^(a^b^c)) + ( w^(a^b^c^d)). So according to the question:
- S%2 == 0 and
- S%(a+b) == 0
So on combining we get S % (2*(a + b)) == 0
Steps were taken to solve the problem:
- Initialize the pointer = 0 variable to iterate over array arr[].
- Calculate prefixXor[] array.
- Initialize array B[] of size N.
- While iterating over the array, if the difference == 2, increment the pointer, otherwise:
- Store arr[pointer] ^ prefixXor[i] in B[i].
- Increment difference by 1.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to generates valid array// according to the given conditionsvoid valid_array_formation(int N, int arr[]){ int prefix_xor[N] = { arr[0] }; // Calculating the prefix xor array for (int i = 1; i < N; i++) { prefix_xor[i] = prefix_xor[i - 1] ^ arr[i]; } int B[N] = { 0 }; // Pointer to extract which element // is to be extracted from array a int pointer = 0; int difference = 0; for (int i = 0; i < N; i++) { // If difference becomes 2 then we // increment the pointer if (difference == 2) { pointer++; difference = 0; } // B[i] i calculated accordingly B[i] = prefix_xor[i] ^ arr[pointer]; difference++; } for (int i = 0; i < N; i++) { // Printing the required array b cout << B[i] << " "; } cout << endl;}// Driver codeint main(){ // Test case 1 int N = 4; int arr1[] = { 2, 6, 1, 5 }; // Function call valid_array_formation(N, arr1); // Test case 2 N = 6; int arr2[] = { 2, 5, 3, 4, 6, 1 }; // Function call valid_array_formation(N, arr2); return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG { // Function to generates valid array // according to the given conditions public static void valid_array_formation(int N, int arr[]) { int prefix_xor[] = new int[N]; prefix_xor[0] = arr[0]; // Calculating the prefix xor array for (int i = 1; i < N; i++) { prefix_xor[i] = prefix_xor[i - 1] ^ arr[i]; } int B[] = new int[N]; // Pointer to extract which element // is to be extracted from array a int pointer = 0; int difference = 0; for (int i = 0; i < N; i++) { // If difference becomes 2 then we // increment the pointer if (difference == 2) { pointer++; difference = 0; } // B[i] i calculated accordingly B[i] = prefix_xor[i] ^ arr[pointer]; difference++; } for (int i = 0; i < N; i++) { // Printing the required array b System.out.print(B[i] + " "); } System.out.println(); } // Driver code public static void main(String args[]) { // Test case 1 int N = 4; int arr1[] = { 2, 6, 1, 5 }; // Function call valid_array_formation(N, arr1); // Test case 2 N = 6; int arr2[] = { 2, 5, 3, 4, 6, 1 }; // Function call valid_array_formation(N, arr2); }}// This Code is Contributed by Prasad Kandekar(prasad264) |
Javascript
// Function to generates valid array// according to the given conditionsfunction validArrayFormation(N, arr) { let prefixXor = [arr[0]]; // Calculating the prefix xor array for (let i = 1; i < N; i++) { prefixXor.push(prefixXor[i - 1] ^ arr[i]); } let B = Array(N).fill(0); // Pointer to extract which element // is to be extracted from array a let pointer = 0; let difference = 0; for (let i = 0; i < N; i++) { // If difference becomes 2 then we // increment the pointer if (difference == 2) { pointer++; difference = 0; } // B[i] i calculated accordingly B[i] = prefixXor[i] ^ arr[pointer]; difference++; } // Printing the required array b console.log(B.join(" "));}// Test case 1let N = 4;let arr1 = [2, 6, 1, 5];// Function callvalidArrayFormation(N, arr1);// Test case 2N = 6;let arr2 = [2, 5, 3, 4, 6, 1];// Function callvalidArrayFormation(N, arr2); |
Python3
# Function to generates valid array# according to the given conditionsdef valid_array_formation(N, arr): prefix_xor = [arr[0]] # Calculating the prefix xor array for i in range(1, N): prefix_xor.append(prefix_xor[i-1] ^ arr[i]) B = [0] * N # Pointer to extract which element # is to be extracted from array a pointer = 0 difference = 0 for i in range(N): # If difference becomes 2 then we # increment the pointer if difference == 2: pointer += 1 difference = 0 # B[i] i calculated accordingly B[i] = prefix_xor[i] ^ arr[pointer] difference += 1 # Printing the required array b print(*B)# Test case 1N = 4arr1 = [2, 6, 1, 5]# Function callvalid_array_formation(N, arr1)# Test case 2N = 6arr2 = [2, 5, 3, 4, 6, 1]# Function callvalid_array_formation(N, arr2) |
C#
using System;public class Program{ // Function to generates valid array // according to the given conditions public static void ValidArrayFormation(int N, int[] arr) { int[] prefixXor = new int[N]; prefixXor[0] = arr[0]; // Calculating the prefix xor array for (int i = 1; i < N; i++) { prefixXor[i] = prefixXor[i - 1] ^ arr[i]; } int[] B = new int[N]; // Pointer to extract which element // is to be extracted from array a int pointer = 0; int difference = 0; for (int i = 0; i < N; i++) { // If difference becomes 2 then we // increment the pointer if (difference == 2) { pointer++; difference = 0; } // B[i] i calculated accordingly B[i] = prefixXor[i] ^ arr[pointer]; difference++; } // Printing the required array b Console.WriteLine(string.Join(" ", B)); } public static void Main() { // Test case 1 int N = 4; int[] arr1 = new int[] { 2, 6, 1, 5 }; // Function call ValidArrayFormation(N, arr1); // Test case 2 N = 6; int[] arr2 = new int[] { 2, 5, 3, 4, 6, 1 }; // Function call ValidArrayFormation(N, arr2); }} |
0 6 3 6 0 5 1 5 5 4
Time Complexity: O(N)
Auxiliary Space : O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!