Tutorialspoint.dev

Sum of matrix element where each elements is integer division of row and column

Consider a N X N matrix where each element is row number divide by column number (integer division), i.e. mat[i][j] = floor((i+1)/(j+1)) where 0 <= i < n and 0 <= j < n. The task is to find the sum of all matrix element.

Examples :

Input  : N = 2
Output : 4
2 X 2 matrix with given constraint:
1 0
2 1
Sum of matrix element: 4

Input  : N = 3
Output : 9



Method 1 (Brute Force):
Run two loops, one for row and another for column and find integer part of (i / j) and add to the answer.

Below is the implementation of this approach:

C++

// C++ program to find sum of matrix element
// where each element is integer division of
// row and column.
#include<bits/stdc++.h>
using namespace std;
  
// Return sum of matrix element where each element
// is division of its corresponding row and column.
int findSum(int n)
{
    int ans = 0;
    for (int i = 1; i <= n; i++)   // for rows
        for (int j = 1; j <= n; j++) // for columns
            ans += (i/j);
    return ans;
}
  
// Driven Program
int main()
{
    int N = 2;
    cout << findSum(N) << endl;
    return 0;
}

Java

// java program to find sum of matrix
// element where each element is integer
// division of row and column.
  
import java.io.*;
  
class GFG {
      
    // Return sum of matrix element 
    // where each element is division
    // of its corresponding row and
    // column.
    static int findSum(int n)
    {
        int ans = 0;
          
        // for rows
        for (int i = 1; i <= n; i++) 
          
            // for columns
            for (int j = 1; j <= n; j++) 
                ans += (i/j);
                  
        return ans;
    }
      
    // Driven Program
    public static void main (String[] args) 
    {
        int N = 2;
        System.out.println( findSum(N));
    }
}
  
// This code is contributed by anuj_67.

Python3

# Python 3 program to find sum of 
# matrix element where each element 
# is integer division of row and column. 
  
# Return sum of matrix element 
# where each element is division 
# of its corresponding row and column. 
def findSum(N):
    ans = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            ans += i // j
    return ans
  
# Driver code
N = 2
print(findSum(N))
  
# This code is contributed 
# by Shrikant13

C#

// C# program to find sum of matrix
// element where each element is integer
// division of row and column.
using System;
  
class GFG {
      
    // Return sum of matrix element 
    // where each element is division
    // of its corresponding row and
    // column.
    static int findSum(int n)
    {
        int ans = 0;
          
        // for rows
        for (int i = 1; i <= n; i++) 
          
            // for columns
            for (int j = 1; j <= n; j++) 
                ans += (i/j);
                  
        return ans;
    }
      
    // Driven Program
    public static void Main () 
    {
        int N = 2;
        Console.WriteLine( findSum(N));
    }
}
  
// This code is contributed by anuj_67.

PHP

<?php
// PHP program to find sum of matrix element
// where each element is integer division of
// row and column.
  
// Return sum of matrix element
// where each element is division 
// of its corresponding row and 
// column.
function findSum( $n)
{
    $ans = 0;
      
    // for rows
    for($i = 1; $i <= $n; $i++) 
      
        // for columns
        for($j = 1; $j <= $n; $j++) 
            $ans += ($i / $j);
    return floor($ans);
}
  
    // Driver Code
    $N = 2;
    echo findSum($N);
      
// This code is contributed by anuj_67.
?>

Output:

4

Method 2 (Efficient):
Let N = 9, matrix will be



Observe, for each jth column
mat[i][k] = 0, for 1 <= k < j, 1 <= i <= N
mat[i][k] = 1, for j <= k < 2*j, 1 <= i <= N
mat[i][k] = 2, for 2*j <= k < 3*j, 1 <= i <= N
and so on.
So, in each column i, there are i – 1 zeroes, followed by i times 1, followed by i times 2 and so on.

We traverse matrix column by column and sum elements.

Below is the implementation of this approach
:

C++

// C++ program to find sum of matrix element
// where each element is integer divison of
// row and column.
#include<bits/stdc++.h>
using namespace std;
  
// Return sum of matrix element where each
// element is division of its corresponding
// row and column.
int findSum(int n)
{
    int ans = 0, temp = 0, num;
  
    // For each column.
    for (int i = 1; i <= n && temp < n; i++)
    {
        // count the number of elements of
        // each column. Initialize to i -1
        // because number of zeroes are i - 1.
        temp = i - 1;
  
        // For multiply
        num = 1;
  
        while (temp < n)
        {
            if (temp + i <= n)
                ans += (i * num);
            else
                ans += ((n - temp) * num);
  
            temp += i;
            num ++;
        }
    }
  
    return ans;
}
  
// Driven Program
int main()
{
    int N = 2;
    cout << findSum(N) << endl;
    return 0;
}

Java

// java program to find sum of matrix element
// where each element is integer divison of
// row and column.
  
import java.io.*;
  
class GFG {
      
    // Return sum of matrix element where each
    // element is division of its corresponding
    // row and column.
    static int findSum(int n)
    {
        int ans = 0, temp = 0, num;
      
        // For each column.
        for (int i = 1; i <= n && temp < n; i++)
        {
              
            // count the number of elements of
            // each column. Initialize to i -1
            // because number of zeroes are i - 1.
            temp = i - 1;
      
            // For multiply
            num = 1;
      
            while (temp < n)
            {
                if (temp + i <= n)
                    ans += (i * num);
                else
                    ans += ((n - temp) * num);
      
                temp += i;
                num ++;
            }
        }
      
        return ans;
    }
      
    // Driven Program
    public static void main (String[] args) 
    {
        int N = 2;
        System.out.println(findSum(N));
    }
}
  
// This code is contributed by anuj_67.

Python3

# Program to find sum of matrix element 
# where each element is integer divison  
# of row and column. 
  
# Return sum of matrix element where each 
# element is division of its corresponding 
# row and column. 
def findSum(n):
    ans = 0; temp = 0;
  
    for i in range(1, n + 1):
  
        # count the number of elements of 
        # each column. Initialize to i -1 
        # because number of zeroes are i - 1. 
        if temp < n:
            temp = i - 1
  
            # For multiply
            num = 1
            while temp < n:
                if temp + i <= n:
                    ans += i * num
                else:
                    ans += (n - temp) * num
                temp += i
                num += 1
    return ans
  
# Driver Code
N = 2
print(findSum(N))
  
# This code is contributed by Shrikant13

C#

// C# program to find sum of matrix 
// element where each element is 
// integer divison of row and column.
using System;
  
class GFG 
{
      
    // Return sum of matrix element 
    // where each element is division 
    // of its corresponding row and column.
    static int findSum(int n)
    {
        int ans = 0, temp = 0, num;
      
        // For each column.
        for (int i = 1; i <= n && temp < n; i++)
        {
              
            // count the number of elements 
            // of each column. Initialize 
            // to i -1 because number of 
            // zeroes are i - 1.
            temp = i - 1;
      
            // For multiply
            num = 1;
      
            while (temp < n)
            {
                if (temp + i <= n)
                    ans += (i * num);
                else
                    ans += ((n - temp) * num);
      
                temp += i;
                num ++;
            }
        }
      
        return ans;
    }
      
    // Driver Code
    public static void Main () 
    {
        int N = 2;
        Console.WriteLine(findSum(N));
    }
}
  
// This code is contributed by anuj_67.

PHP

<?php
// PHP program to find sum of 
// matrix element where each 
// element is integer divison 
// of row and column.
  
// Return sum of matrix element 
// where each element is division 
// of its corresponding row and column.
function findSum( $n)
{
    $ans = 0; $temp = 0; $num;
  
    // For each column.
    for ($i = 1; $i <= $n and 
         $temp < $n; $i++)
    {
        // count the number of elements 
        // of each column. Initialize 
        // to i -1 because number of 
        // zeroes are i - 1.
        $temp = $i - 1;
  
        // For multiply
        $num = 1;
  
        while ($temp < $n)
        {
            if ($temp + $i <= $n)
                $ans += ($i * $num);
            else
                $ans += (($n - $temp) *     
                                $num);
  
            $temp += $i;
            $num ++;
        }
    }
  
    return $ans;
}
  
// Driver Code
$N = 2;
echo findSum($N);
  
// This code is contributed by anuj_67.
?>

Output :

3

Source: http://stackoverflow.com/questions/41094769/sum-of-integer-division-matrix?rq=1

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter