Generate Array whose average and bitwise OR of bitwise XOR are equal

By Ann Roberts On Dec 7, 2022

Improve Article

Save Article

Like Article

Improve Article

Save Article

Given an integer N (N is odd). the task is to construct an array arr[] of size N where 1 ≤ arr[i] ≤ N such that the bitwise OR of the bitwise XOR of every consecutive pair should be equal to the average of the constructed arr[]. Formally:

(arr[0] ^ arr[1]) | (arr[2] ^ arr[3] ) | (arr[4] ^ arr[5]) . . . (arr[N-3] ^ arr[N-2] ) | arr[N-1] = ( arr[0] + arr[1] + arr[2] . . . +a[N-1]) / N

where ^ is the bitwise Xor and | is the bitwise Or.

Note: If there are multiple possible arrays, print any of them.

Examples:

Input: N = 1
Output: arr[] = {1}
Explanation:- Since n=1 hence an=1 and the average of these numbers is also 1.

Input: n = 5
Output: arr[] = {1, 2, 4, 5, 3}
Explanation: (1^2) | (4^5) | 3 = 3 and (1+2+3+4+5)/5 = 3. Hence it forms a valid integer array.

Approach: Implement the idea below to solve the problem:

XOR of two same values gives you 0. OR operation with a number will give you the same number. So, if we assign all values to X, then all the XOR values will be 0 except for the last element which does not form any pair. So the Xor will be X. Also the average will become N*X/N = X.

Follow the below steps to implement the idea:

Initialize the array of size N.
Assign each element of the array as any value X (where X is in the range of [1, N]).

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

void valid_array_formation(int N)

{

int arr[N];

for (int i = 0; i < N; i++) {

arr[i] = N;

}

for (int i = 0; i < N; i++) {

cout << arr[i] << " ";

}

cout << endl;

}

int main()

{

int N = 1;

valid_array_formation(N);

N = 5;

valid_array_formation(N);

return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(N)

Improve Article

Save Article

Like Article

Improve Article

Save Article

(arr[0] ^ arr[1]) | (arr[2] ^ arr[3] ) | (arr[4] ^ arr[5]) . . . (arr[N-3] ^ arr[N-2] ) | arr[N-1] = ( arr[0] + arr[1] + arr[2] . . . +a[N-1]) / N

where ^ is the bitwise Xor and | is the bitwise Or.

Note: If there are multiple possible arrays, print any of them.

Examples:

Input: N = 1
Output: arr[] = {1}
Explanation:- Since n=1 hence an=1 and the average of these numbers is also 1.

Input: n = 5
Output: arr[] = {1, 2, 4, 5, 3}
Explanation: (1^2) | (4^5) | 3 = 3 and (1+2+3+4+5)/5 = 3. Hence it forms a valid integer array.

Approach: Implement the idea below to solve the problem:

XOR of two same values gives you 0. OR operation with a number will give you the same number. So, if we assign all values to X, then all the XOR values will be 0 except for the last element which does not form any pair. So the Xor will be X. Also the average will become N*X/N = X.

Follow the below steps to implement the idea:

Initialize the array of size N.
Assign each element of the array as any value X (where X is in the range of [1, N]).

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

void valid_array_formation(int N)

{

int arr[N];

for (int i = 0; i < N; i++) {

arr[i] = N;

}

for (int i = 0; i < N; i++) {

cout << arr[i] << " ";

}

cout << endl;

}

int main()

{

int N = 1;

valid_array_formation(N);

N = 5;

valid_array_formation(N);

return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(N)

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.