In this HackerRank XOR Matrix problem solution, we have a zero-indexed matrix with M rows and N columns, where each row is filled gradually. given the first row of the matrix, we need to generate the elements in the subsequent rows using the formula. and each row is generated one by one from the second row through the last row. we have given the first row of the matrix, find and print the elements of the last row as a single line of space-separated integers.
Problem solution in Python.
#!/bin/python3 import os import sys def xorMatrix(m, first_row): n = len(first_row) m -= 1 # now 0 row is first row, 1 row is the first row to compute mb = str(bin(m))[2:] lmb = len(mb) result = first_row.copy() for i in range(lmb): if mb[i] == '1': tmp = result.copy() offset = 2 ** (lmb - 1 - i) for j in range(n): result[j] = tmp[j] ^ tmp[(j + offset) % n] return result if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') nm = input().split() n = int(nm[0]) m = int(nm[1]) first_row = list(map(int, input().rstrip().split())) last_row = xorMatrix(m, first_row) fptr.write(' '.join(map(str, last_row))) fptr.write('n') fptr.close()
Problem solution in Java.
import java.io.*; import java.math.*; import java.text.*; import java.util.*; import java.util.regex.*; public class Solution { static int[] firstRow; static int[] nextRow; static void next(long count) { for (int i = 0; i < firstRow.length; i++) { nextRow[i] = firstRow[i] ^ firstRow[(int) ((count + i) % firstRow.length)]; } int[] temp = firstRow; firstRow = nextRow; nextRow = temp; } static int[] xorMatrix(long m) { long pos = 1; while (pos < m) { long lowerPowerOfTwo = 1; while (pos + 2 * lowerPowerOfTwo <= m) { lowerPowerOfTwo *= 2; } next(lowerPowerOfTwo); pos += lowerPowerOfTwo; } return firstRow; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); long m = Long.parseLong(st.nextToken()); firstRow = new int[n]; nextRow = new int[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { int item = Integer.parseInt(st.nextToken()); firstRow[i] = item; } int[] result = xorMatrix(m); for (int i = 0; i < n; i++) { if (i > 0) { bw.write(" "); } bw.write(String.valueOf(result[i])); } bw.newLine(); bw.close(); br.close(); } }
Problem solution in C++.
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define N 60 #define ll long long int main() { ll m, st; ll n, x, y; vector<vector<ll>> a; a.resize(2); cin >> n >> m; m--; a[0].resize(n); a[1].resize(n); for (int i = 1; i <= n; i++) { cin >> a[0][i]; } x = 1; y = 0; while (m) { swap(x, y); for (int i = N; i >= 0; i--) { if (m >= ((ll)1 << i)) { st = ((ll)1 << i); break; } } m -= st; for (int i = 1; i <= n; i++) { a[y][i] = a[x][i] ^ a[x][(i + st - 1) % n + 1]; } } for (int i = 1; i <= n; i++) { cout << a[y][i] << " "; } return 0; }
Problem solution in C.
#include <assert.h> #include <limits.h> #include <math.h> #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdint.h> void iterate ( size_t const offset, size_t const count, uint32_t ** entry_ref, uint32_t ** spare_ref ) { uint32_t * entries = * entry_ref; uint32_t * spares = * spare_ref; for ( size_t i = 0; i < count; ++i ) spares [i] = entries [i] ^ entries [(i+offset)%count]; * entry_ref = spares; * spare_ref = entries; } int main() { size_t count = 0; scanf ( "%zu", &count ); size_t rows = 0; scanf ( "%zu", &rows ); uint32_t * entries = (uint32_t *) malloc (count * sizeof(uint32_t)); uint32_t * spares = (uint32_t *) malloc (count * sizeof(uint32_t)); for ( size_t i = 0; i < count; ++i ) { unsigned entry = 0; scanf ( "%u", &entry ); entries [i] = entry; } for ( size_t bit_map = rows - 1; bit_map; bit_map &= bit_map - 1 ) { size_t const low_bit = ((size_t) 1) << __builtin_ctzll ( bit_map ); iterate ( low_bit, count, &entries, &spares ); } for ( size_t i = 0; i < count; ++i ) printf ( "%u ", (unsigned) entries [i] ); return 0; }