if(n==m) matrix will be symmetric so XOR of all elements except diagonal will become 0 and answer will be simply the xor of diagonal elements
if(n!=m) except the elements a[0][0] and a[n-1][m-1] all elements will be repeated twice so XOR=0 so answer should be the XOR of a[0][0] and a[n-1][m-1].
the sum of N over all test cases does not exceed 2\cdot10^6\implies \sum\limits_{t}N <= 2 \cdot10^6
the sum of M over all test cases does not exceed 2\cdot10^6\implies \sum\limits_{t}M <= 2 \cdot10^6
One way to view this, for consideration of the worst case for N and M, is to consider T = 1 and devise your algorithm.
Now we can satisfy all the four constraints, and understand that we need a linear time solution.
My code with very easy logic please refer it
Algorithm
Traverse loop from 2 to m+n
check if number of daigonal of number s present odd number of times then push i+k in vector
3.traverse vector and take xor of all element in vector
example
m=4 n=3 k=4;
then 2d representation look like
2 3 4
3 4 5
4 5 6
5 6 7
like if we traverse from 2 to 7
for 2 it is present odd time push i+k in vector
for 3 it is present even time so it cant be pushed
here is my code do upvote my answer guys if you find it helpful thank you
#include<bits/stdc++.h> #define REP(i,n) for (int i = 1; i <= n; i++) #define mod 1000000007 #define pb push_back #define ff first #define ss second #define ii pair<int,int> #define vi vector #define vii vector #define ll long long int #define INF 1000000000 #define endl ‘\n’
const double PI = 3.141592653589793238460;
typedef std::complex Complex;
typedef std::valarray CArray;
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll test;
cin>>test;
while(test–)
{
int n,m,k;
cin>>n>>m>>k;
long long int ans = 0;
int row = 1;
vector array;
for(int i = 2;i<=n+m;i++)
{
if(i-row>m)
{
row++;
}
int c = i-row;
int d = c;
if(d+row>n)
{
d = n-row+1;
}
if(d&1)
{
array.push_back(i+k);
}
}
long long int A = 0;
if(array.size()>1)
{
for(int i = 0 ;i<array.size();i++)
{
A = A^array[i];
}
}
cout<<A<<endl;
}
See this solution for O(1) approach.
You can find xor of a range in O(1) (link 1) & xor of alternate elem of a range in O(1) (link 2).
Now consider rows pairwise (eg 1 & 2 ; 3 & 4 and so on). You can see that by xoring a pair (eg: 1 & 2) you will get (A[1][1] ^ A[2][m]) i.e for each pair of rows it boils down to xor of just 2 elem. Okay 1 dimension reduced i.e O(n) complexity. 1 more to go.
If you see first value of result of all such pairs they form a sequence with a difference of 2. Similarly second value of result of all such pairs form a sequence with a difference of 2. Both of these can be evaluated in O(1) using link 2.
Edge case: When n is odd, one row will be left after considering rows pairwise which we can handle separately in O(1) using link 1.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while (t–)
{
/* code /
int N,M,K;
cin>>N>>M>>K;
int matrix[N][M];
int xor_matrix=0;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
matrix[i][j]=i+j+K;
xor_matrix^=(*(matrix+i)+j);
}
}
cout<<xor_matrix<<"\n";
}
return 0;
}
Can someone tell me why is this code giving runtime error for the second test case.(any help would be helpful)
#include <bits/stdc++.h>
using namespace std; #define ll long long int #define llv vector #define line cout<<"\n" #define MOD 1000000007 #define forloop for(i=0;i<n;i++) #define FASTIO ios_base::sync_with_stdio(false);cin.tie(0),cout.tie(0);
int main() {
ll t;
cin>>t;
while(t–)
{
int n,m,k;
int a=0,i;
cin>>n>>m>>k;
//for even
for(i=1;i<n;i+=2) // at most n times
a=a^(i+1+k);
for(i=2;i<=n;i+=2)
a=a^(i+m+k);
//if n is odd then do xor for last row also
if(n%2 !=0)
{
for(i=1;i<=m;i++) // at most m times
a=a^(n+i+k);
}
cout<<a<<"\n";
}
why it is giving wa for my code
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,m,k,sum=0;
cin>>n>>m>>k;
sum=(k+2)^(k+m+n);
for(int i=2;i<=n;i++)
{
if(k+i+1<=k+m+1)
{
if(i%2==1)
{
sum=(sum)^(k+i+1);
}
}
else
{
int p=(k+i+1)-(k+m+1);
int c=i-§;
if(c%2==1)
{
sum=sum^(k+i+1);
}
}
}
int z=(k+m+n)-2;
while(z>k+n+1)
{
sum=sum^z;
z=z-2;
}
cout<<sum<<endl;
}
}
The answer is coming out to be correct but its taking quite a long time to finish. Please can someone tell me how to use less for loops and solve this.
num = int(input())
list1 = []
while num > 0:
n, m, k = map(int, input().split())
for i in range(1, n+1):
for j in range(1, m+1):
list1.append(i+j+k)
num = num - 1
xor = list1[0]
for i in range(1, len(list1)):
xor = xor ^ list1[i]
print(xor)