C++ program to find last value of matrix with given constraints

Suppose we have a list of numbers A with N elements in it. The elements are 1, 2 or 3, Consider a number X[1][j] = A[j] where j is in range 1 to N. And X[i][j] = |X[i-1][j] - X[i-1][j+1]| where i is in range 2 to N and j is in range 1 to N+1-i. We have to find the value of X[i][j].

So, if the input is like A = [1,2,3,1], then the output will be 1, because

X[1][1] to X[1][4] are 1, 2, 3, 1 X[2][1], X[2][2], X[2][3] are |1-2| = 1, |2 - 3| = 1 and |3 - 1| = 2 X[3][1], X[3][2] are ? 1 − 1? = 0, ? 1 − 2? = 1. X[4][1] = |0 - 1| = 1 So the answer is 1

To solve this, we will follow these steps −

Define a function calc(), this will take N, M, cnt := 0 for initialize k := N, when k is non-zero, update k >>= 1, do:    cnt := floor of (cnt + k)/2 for initialize k := M, when k is non-zero, update k >>= 1, do:    cnt := floor of (cnt - k)/2 for initialize k := N - M, when k is non-zero, update k >>= 1, do:    cnt := floor of (cnt - k)/2 return invert of cnt From the main method, do the following n := size of A Define an array arr of size (n + 1) for initialize i := 1, when i < n, update (increase i by 1), do:    arr[i - 1] = |A[i] - A[i - 1]| (decrease n by 1) hh := 1, pd := 0, ck := 0 for initialize i := 0, when i < n, update (increase i by 1), do:    if arr[i] is non-zero, then:     if arr[i] is same as 1, then: hh := 0 pd := pd XOR calc(n - 1, i) Otherwise ck := ck XOR calc(n - 1, i) ck := ck AND hh if pd XOR ck is non-zero, then: return "1" + hh return "0"

Example

Let us see the following implementation to get better understanding −

#include <bits/stdc++.h> using namespace std; int calc(int N, int M) {    int cnt = 0;    for (int k = N; k; k >>= 1)       cnt += k >> 1;    for (int k = M; k; k >>= 1)       cnt -= k >> 1;    for (int k = N - M; k; k >>= 1)       cnt -= k >> 1;    return !cnt; } string solve(vector<int> A) {    int n = A.size();    vector<int> arr(n + 1);    for (int i = 1; i < n; i++) {     arr[i - 1] = abs(A[i] - A[i - 1]); } --n; bool hh = 1, pd = 0, ck = 0; for (int i = 0; i < n; i++) if (arr[i]) { if (arr[i] == 1) hh = 0, pd ^= calc(n - 1, i); else ck ^= calc(n - 1, i); } ck &= hh; if (pd ^ ck) return "1" + hh; return "0"; } int main(){ vector<int> A = { 1, 2, 3, 1 }; cout << solve(A) << endl; }

Input

{ 1, 2, 3, 1 }

Output

1