Program for the Multiplication of Two 2D Matrix.

In this post, we are going to learn the process of multiplication of two 2D arrays and display the resulting array on screen. 

Example:

Multiplication of Matrices

Below are a few points to keep in mind before performing Matrix Multiplication:

• Matrix multiplication is only possible when the number of columns of the first matrix should be equal to the number of rows of the second matrix. 
• In matrix multiplication, the product of an m x k matrix and k x n matrix is an m x n matrix.
• Matrix multiplication is not commutative in nature, it means the order multiplication of two matrices matters and can change our result.
• Each entry in the resulting matrix is the dot product of row elements of the first matrix with column elements of the second matrix.

Below is C++ Code Implementation:

//Program to for Multiplication of 2D Array (Matrix)
#include<iostream>
using namespace std;

int main(){
    int arr1[50][50], arr2[50][50], prod[50][50] = {0};
    int row1, col1, row2, col2;
    //column of first matrix should be equal to row of second matrix
    do{
        cout<<"Enter number of rows and columns for first matrix: ";
        cin>>row1>>col1;

        cout<<"Enter number of rows and columns for second matrix: ";
        cin>>row2>>col2;
    }while(col1 != row2);
    
    //Taking input for first matrix
    cout<<"Enter the elements of first Array: "<<endl;
    for(int i = 0; i < row1; i++){
        for(int j = 0; j < col1; j++){
            cout<<"Enter element for position arr["<<i<<"]["<<j<<"] = ";
            cin>>arr1[i][j];
        }
    }
    //Taking input for second matrix
    cout<<"Enter the elements of second Array: "<<endl;
    for(int i = 0; i < row2; i++){
        for(int j = 0; j < col2; j++){
            cout<<"Enter element for position arr["<<i<<"]["<<j<<"] = ";
            cin>>arr2[i][j];
        }
    }
    //Multiplication of Matrix
    cout<<"The Multiplication of two Matrices: "<<endl;
    for(int i = 0; i < row1; i++){
        for(int j = 0; j < col2; j++){
            for(int k = 0; k < col1; k++){
                prod[i][j] = arr1[i][k] * arr2[k][j];
            }
        }
    }

    cout<<"Displaying Product of Two Matrix: "<<endl;
    for(int i = 0; i < row1; i++){
        for(int j = 0; j < col2; j++){
            cout<<prod[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

Output:

Enter number of rows and columns for first matrix: 2 3
Enter number of rows and columns for second matrix: 3 2
Enter the elements of first Array: 
Enter element for position arr[0][0] = 1
Enter element for position arr[0][1] = 2
Enter element for position arr[0][2] = 3
Enter element for position arr[1][0] = 4
Enter element for position arr[1][1] = 5 
Enter element for position arr[1][2] = 6
Enter the elements of second Array: 
Enter element for position arr[0][0] = 6
Enter element for position arr[0][1] = 5
Enter element for position arr[1][0] = 4
Enter element for position arr[1][1] = 3
Enter element for position arr[2][0] = 2
Enter element for position arr[2][1] = 1
The Multiplication of two Matrices: 
6 3
12 6

In the above code, we have taken the first matrix of size 2 x 3 and the second matrix of size 3 x 2 and the resultant matrix that we get after multiplication is of size 2 x 2 which is satisfying our matrix property.

Next:

(getButton) #text=(Program for Addition of Two 2D Matrices) #icon=(link) #color=(#2339bd)

Program for the Addition of Two 2D Matrix.

In this post, we will learn how to add two (2D arrays) matrices and print them in the form of a single Matrix of the same size. Before moving directly to the program, let's first understand how this addition of two matrices happened and what the conditions record required for this operation. 

Note: A matrix can be used for addition or subtraction with another matrix only if both matrices have the same dimensions which means that both matrices should have an equal number of rows and the equal number of columns. (alert-success) 

Example: 

Matrix Addition

Below is the C++ Code Implementation:

//C++ Program to for Addition of 2D Array (Matrix)
#include<iostream>
using namespace std;

int main(){
    int arr1[50][50], arr2[50][50], sum[50][50];
    int row, col;
    
    cout<<"Enter number of rows: ";
    cin>>row;

    cout<<"Enter number of column: ";
    cin>>col;
    //Taking input for first matrix
    cout<<"Enter the elements of first Array: "<<endl;
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            cout<<"Enter element for position arr["<<i<<"]["<<j<<"] = ";
            cin>>arr1[i][j];
        }
    }
    //Taking input for second matrix
    cout<<"Enter the elements of second Array: "<<endl;
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            cout<<"Enter element for position arr["<<i<<"]["<<j<<"] = ";
            cin>>arr2[i][j];
        }
    }
    

    //Addition of Matrix  
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            sum[i][j] = arr1[i][j] + arr2[i][j];
        }
    }

    cout<<"Displaying Sum of Two Matrix: "<<endl;
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            cout<<sum[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

Output:

Enter number of rows: 3
Enter number of column: 3
Enter the elements of first Array: 
Enter element for position arr[0][0] = 2
Enter element for position arr[0][1] = 3
Enter element for position arr[0][2] = 6
Enter element for position arr[1][0] = 1
Enter element for position arr[1][1] = 4
Enter element for position arr[1][2] = 1
Enter element for position arr[2][0] = 9
Enter element for position arr[2][1] = 2
Enter element for position arr[2][2] = 5
Enter the elements of second Array: 
Enter element for position arr[0][0] = 1
Enter element for position arr[0][1] = 2
Enter element for position arr[0][2] = 3
Enter element for position arr[1][0] = 4
Enter element for position arr[1][1] = 5
Enter element for position arr[1][2] = 6
Enter element for position arr[2][0] = 7
Enter element for position arr[2][1] = 8
Enter element for position arr[2][2] = 9
Displaying Sum of Two Matrix: 
3 5 9
5 9 7
16 10 14

In the above code, we have taken two 3x3 matrices for addition, and after adding we have stored our result in a sum matrix which is of the same 3x3 size. 

In the same way, you can write a program for the subtraction of two matrices, you just need to change the arithmetic operation from addition to subtraction and everything else will remain the same as it is.

Next:

(getButton) #text=(Program for Multiplication of Two Matrix) #icon=(link) #color=(#2339bd)

Program to Find Duplicate Element of an Array.

Given a positive integer array of sizes n and we need to find the element that appears more than one time in the given array. If no such element is present then return -1.

Example 1:

Input: arr[] = {9, 2, 7, 3, 10, 2}
Output: 2

Explanation: 2 appears more than one times.

Input: arr[] = {4, 2, 7, 3, 10, 21}
Output: -1
Explanation: All elements are unique, not duplicate element found.

Approach 1: Brute Force.

We can find the duplicate element in the given array but run two nested loops where the first loop will pick the element one by one and the inner loop will compare that element with all remaining elements of the array to check if any duplicate element exists.

Steps to solve the problem:

• Run two nested loops, the first loop will run from i = 0 to i = n-1 and the second loop will run from j = i+1 to j = n-1.
• If at any moment, arr[i] == arr[j] it means a duplicate element exist,s and then prints the duplicate element.

C++ code Implementation:

//C++ code to find duplicate elements of array
#include<bits/stdc++.h>
using namespace std;

//function to find duplicate element in array
int duplicate(int arr[], int n){
    int ans;

    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(arr[i] == arr[j]){
                ans = arr[i];
                break;
            }
        }
    }
    return ans;
}

int main(){
    
    int arr[] = {9, 2, 7, 3, 10, 2};
    //size of the given array
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout<<"The element present more than one time: "<<duplicate(arr, n);

    return 0;
}

Output:

The element present more than one time: 2

• Time Complexity: O(n^2) 
• Space Complexity: O(1)

Approach 2: Using a Hash Table (Optimized).

For this approach, we are going to use an unordered map (internally implemented using Hash Table) that is an associated container used to store data in the form of Key and Value pair. 

Steps to solve the problem:

• Declare a unordered_map<int, int> in which the key and value type is an integer. 
• Traverse the array and take each element as Key and store their count as a value to that key.
• If you found any key with a value greater than 1 then it means there exists a duplicate element in the array.
• Print that key with having count greater than 1.

C++ code Implementation:

//C++ code to find duplicate elements of array using Hash Table
#include<bits/stdc++.h>
using namespace std;

//function to find duplicate element in array
int duplicate(int arr[], int n){
    int ans;
    unordered_map<int, int> mp{0};

    for(int i = 0; i < n; i++){
        mp[arr[i]]++;
    }

    for(auto it: mp){
        if(it.second > 1){
          ans = it.first;
          break;
        }    
    }
    return ans;
}

int main(){
    
    int arr[] = {9, 2, 7, 3, 10, 2};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout<<"The element present more than one times: "<<duplicate(arr, n);

    return 0;
}

Output:

The element present more than one time: 2

• Time Complexity: O(n) As we need to traverse the array only one time to get the count of each unique element and there is no nested loop required. 
• Space Complexity: O(n) As we are using extra n space for storing the count of each unique element. 

Also see:

(getButton) #text=(Program to Reverse Array Elements) #icon=(link) #color=(#2339bd)

(getButton) #text=(Program to Find Kth Smallest Element of an Array) #icon=(link) #color=(#2339bd)

Program to Reverse an Array Elements In Place.

Given an array of sizes n and we need to reverse all array elements in place and print the reverse array. 

Note: The task is to reverse the array in place so that when we print the same array the array elements should be in reverse order.

{2, 4, 8, 1, 9} --- Reverse --- {9, 1, 8, 4, 2}

Example:

Input: arr[] = {9, 2, 7, 3, 10}
Output: arr[] = {10, 3, 7, 2, 9}

Approach: Using Iterative way (Brute Force)

Steps to solve the problem:

• Declare two variables, start = 0 and end = n-1 where n is the size of the given array.
• Run a while loop and keep swapping arr[start] and arr[end] and after each swap increment the value of start = start + 1 and decrement the value of end  = end - 1. 
• Break the loop condition as soon as start >= end.

C++ code Implementation:

//C++ code to reverse the array elements
#include<bits/stdc++.h>
using namespace std;

//function to reverse array
void reverseArray(int arr[], int n){

    int start = 0, end = n - 1;

    while(start < end){
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

int main(){
    
    int arr[] = {9, 2, 7, 3, 10};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    reverseArray(arr, n);

    for(int i = 0; i < n; i++){
        cout<<arr[i]<<" ";
    }

    return 0;
}

Output:

10, 3, 7, 2, 9

• Time Complexity: O(n)
• Space Complexity: (1)

Also see:

(getButton) #text=(Program to Find Kth Smallest Element of an Array) #icon=(link) #color=(#2339bd)

Program to Find the Smallest and Largest Element of an Array.

Given an array of sizes n and we need to find the maximum and minimum number present in the given array.

Example:

Input: arr[] = {12, 9, 2, 7, 3, 10}
Output: 

Maximum: 12

Minimum: 2

Input: arr[] = {5, 9, -2, 23, 7, 10}
Output: 

Maximum: 23
Minimum: -2

Approach 1: Brute Force approach.

In this approach, we traverse the entire array and pick each element one by one to compare the smallest and largest element. 

Following steps to solve the problem:

1. Declare two variables max_value and min_value and initialize max_value with 2. INT_MIN and min_value with INT_MAX.

3. Traverse the array and

• Update the value of max_value if you found any value greater than the current max_value. 
• Update the value of min_value if you found any value greater than the current min_value. 

4. Print maximum and minimum values.

Below is the C++ code Implementation:

//C++ code to find the maximum and minimum value of an array
#include<iostream>
using namespace std;

//function to print maximum and minimum value
void largeSmall(int arr[], int n){
   int max_value = INT_MIN;
   int min_value = INT_MAX;

   for(int i = 0; i < n; i++){
    //checking max value
    if(arr[i] > max_value)
       max_value = arr[i];
    //checking min value   
    if(arr[i] < min_value)
       min_value = arr[i];   
   }

   cout<<"Maximum: "<<max_value<<endl;
   cout<<"Minimum: "<<min_value<<endl;
}

int main(){
    
    int arr[] = {12, 9, -2, 7, 3, 10};
    //size of the given array
    int n = sizeof(arr)/sizeof(arr[0]);
    //function call
    largeSmall(arr, n);
    return 0;
}

Output:

Maximum: 12
Minimum: -2

• Time Complexity: O(n)
• Space Complexity: O(1)

Approach 2: Using Recursion.

1. In the recursive approach, we made two different function call for maximum and minimum. 

if(n == 1) 

   return arr[0]

2. This is our base case which indicates that when you traverse the complete array and only one element is left in the array then we can simply return arr[0].

3. Recursively we are reducing the size of the array in each recursive call (n-1) and trying to store the maximum so far.  

Below is the C++ code Implementation:

//C++ Recursive code to find the maximum and minimum value of an array
#include<iostream>
using namespace std;

//recursive function to return maximum value
int largestNum(int arr[], int n){
  //base case when we traverse the complete array
  if(n == 1)
    return arr[0];

  return max(arr[n-1], largestNum(arr, n-1));  
}

//recursive function to return the minimum value
int smallestNum(int arr[], int n){
  //base case when we traverse the complete array
  if(n == 1)
    return arr[0];

  return min(arr[n-1], smallestNum(arr, n-1));  
}

int main(){
    
    int arr[] = {12, 9, -2, 7, 3, 10};
    //size of the given array
    int n = sizeof(arr)/sizeof(arr[0]);
    //function call
    cout<<"Maximum: "<<largestNum(arr, n)<<endl;
    cout<<"Minimum: "<<smallestNum(arr, n)<<endl;
    return 0;
}

Output:

Maximum: 12
Minimum: -2

• Time Complexity: O(n)
• Space Complexity: O(1)

Approach 3: Using Library Function.

In most programming languages there are several built-in functions to use for finding the maximum and minimum of an array. In C++ we have max_element() and min_element() library function.

Below is the C++ code Implementation:

//C++ code to find maximum and minimum value of an array
#include<bits/stdc++.h>
using namespace std;

//library function to return maximum value
int largestNum(int arr[], int n){
    return *max_element(arr, arr+n);
}

//library function to return minimum value
int smallestNum(int arr[], int n){
  return *min_element(arr, arr+n);
}

int main(){
    
    int arr[] = {12, 9, -2, 7, 3, 10};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    //function call
    cout<<"Maximum: "<<largestNum(arr, n)<<endl;
    cout<<"Minimum: "<<smallestNum(arr, n)<<endl;
    return 0;
}

Output:

Maximum: 12
Minimum: -2

• Time Complexity: O(n)
• Space Complexity: O(1)

Also see:

(getButton) #text=(Program to Find Kth Largest Element of an Array) #icon=(link) #color=(#2339bd)

(getButton) #text=(Program to Find Kth Smallest Element of an Array) #icon=(link) #color=(#2339bd)

Program to Find Kth Smallest Element of an Array.

Given an array of n distinct elements and we need to find the kth smallest element from the given array where the value of k is larger than the size of the given array.

Example:

Input: arr[] = {12, 9, 2, 7, 3, 10}, k = 2
Output: 3

Input: arr[] = {12, 9, 2, 7, 3, 10}, k = 5
Output: 10

There are multiple ways in which you can solve this basic level array problem and here we are going to discuss two different ways to find the kth smallest element of an array. 

Approach 1: Using Sorting.

The brute force approach that we can think of is to sort the given array in ascending order and return the element present at index (k-1) and array elements are stored based on 0-based indexing. You can use the Quick sort algorithm to sort the array whose time complexity is O(nlogn).

In C++, we have one sort member function that sorts the array in ascending order by default and the internally implemented quick sort algorithm. 

C++ Code Implementation:

//C++ code to find the kth smallest element of an array
#include<iostream>
#include<algorithm>
using namespace std;

//function to return kth smallest element
int smallestNumber(int arr[], int n, int k){
    //sort the array
    sort(arr, arr+n);

    return arr[k-1];
}

int main(){
    
    int arr[] = {12, 9, 2, 7, 3, 10};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 2;
    cout<<"The kth smallest element is: "<<smallestNumber(arr, n, k); 

    return 0;
}

Output:

The kth smallest element is: 3

• Time Complexity: O(nlogn)
• Space Complexity: O(1)

Approach 2: Using Set data structure.

The set data structure is used to store unique elements of same type in sorted order. As mentioned in the question itself that all elements are distinct which means if we store them in a set data structure we can easily find the kth smallest element. 

• The drawback of using set data structure is that we required n extra spaces to sort the given array which increase the space complexity to O(n).

C++ Code Implementation:

//C++ code to find kth smallest element of an array using set
#include<bits/stdc++.h>
using namespace std;

//function to return kth smallest element
int smallestNumber(int arr[], int n, int k){
    //set data structure
    set<int> s(arr, arr+n);
    //pointer to first element
    set<int>::iterator it = s.begin();
    advance(it, k-1);

    return *it;
}

int main(){
    
    int arr[] = {12, 9, 2, 7, 3, 10};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 5;
    cout<<"The kth smallest element is: "<<smallestNumber(arr, n, k); 

    return 0;
}

Output:

The kth smallest element is: 10

• Time Complexity: O(nlogn)
• Space Complexity: O(n)

Next: (getButton) #text=(Program to Find Kth Largest Element of an Array) #icon=(link) #color=(#2339bd)