1 day ago

Sarthak • 10

Hyderabad

Question: Matrix Element Replacement (Nearest Divisible by 5)

Problem Statement:

Consider A is a square matrix with size N. Write a program to replace every element A[i][j] of the matrix with a number that is nearest to or equal to A[i][ j] divisible by 5.

Read the input from STDIN and write the output to STDOUT. You should not write arbitrary strings while reading the input and while printing as these contribute to the standard output.

Constraints:

1. 1 < N < 50
2. Each row of the output matrix should end with a single whitespace.

Input Format:

• The first line of input contains an integer N, the size of the matrix.
• The next N lines contain N integers each separated by a single whitespace.

Output Format:

• The output should print the N \times N matrix, where each element is nearest or equal to A[i][j] and divisible by 5. Elements in each row should be separated by a single whitespace, and each row should end with a single whitespace.

Sample Input 1:

2

1 8

3 6

Sample Output 1:

0 10

5 5

Explanation 1:

From the Sample Input 1, we have:

2

1 8

3 6

• For 1, the nearest multiple of 5 is 0.
• For 8, the nearest multiple of 5 is 10.
• For 3, the nearest multiple of 5 is 5.
• For 6, the nearest multiple of 5 is 5.
  (Note: If a number is exactly exactly between two multiples, the nearest logic will apply based on standard rounding, though typically the problem expects standard absolute difference minimization).

9 hours ago

admin 1.9k

Hyderabad

Matrix Element Replacement Solution

Topics Involved / Prerequisites

• Matrix Traversal
• Modular Arithmetic

Overview

• To find the nearest multiple of 5, we can use the remainder of the number when divided by 5 to determine the optimal rounding direction.
• If the remainder's absolute value is strictly greater than 2, we round the quotient away from zero to the next nearest multiple.
• Otherwise, the number is close enough to round directly down to its current quotient multiplied by 5.

Approach

1. The Mathematics of Rounding

Using modulo arithmetic avoids floating-point inaccuracies. We calculate the quotient q = x / 5 and remainder r = x % 5. For positive numbers, if r > 2, the nearest multiple is (q + 1) * 5. For negative numbers, if r < -2, the nearest multiple is (q - 1) * 5. Otherwise, the nearest multiple is simply q * 5.

2. On-the-Fly Processing

Since we only need to print the transformed matrix, we do not need to store the entire N \times N matrix in memory. We can read each element, instantly compute its nearest multiple of 5, and print it directly to the standard output, ensuring the spatial complexity remains absolute minimal.

C++ code implementation -: 

#include <iostream>

using namespace std;

int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    // Read the size of the matrix. If no input, exit safely.
    if (!(cin >> n)) return 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int x;
            cin >> x;
            
            int q = x / 5;
            int r = x % 5;
            
            int nearest;
            // Handle positive rounding up
            if (r > 2) {
                nearest = (q + 1) * 5;
            } 
            // Handle negative rounding down
            else if (r < -2) {
                nearest = (q - 1) * 5;
            } 
            // Round to the current quotient
            else {
                nearest = q * 5;
            }
            
            // Print the element followed by a single whitespace
            cout << nearest << " ";
        }
        // Print a newline at the end of each row
        cout << "\n";
    }

    return 0;
}

Time and space Complexity

• Time: O(N^2) - We process every element of the N \times N matrix exactly once as we read it from the input stream.
• Space: O(1) - We process and print the elements on the fly without storing the 2D grid in memory.