Program to Find Intersection of Two Arrays.

Given two integer arrays arr1[] and arr2[], the task is to find the intersection of two given arrays. The resulting array must contain only unique elements and you may return the result in any order.

Example:

Input: arr1 = [1, 2, 2, 1], arr2 = [2, 2]
Output: [2]

Input: arr1 = [4, 9, 5], arr2 = [9, 4, 9, 8, 4]
Output: [9, 4]

Input: arr1 = [1, 2, 3, 4], arr2 = [5, 6, 7, 8]
Output: []

Note: The intersection of two arrays is the set of elements that are common to both arrays, without any duplicates.

There are many approaches to finding the intersection of two arrays and here we are going to discuss each approach in detail with code. 

Approach 1: Brute Force Approach.

This is a straightforward approach to find the intersection where each element in the first array (arr1) is checked against every element in the second array (arr2). If a match is found, the element is added to the result array.

Step-by-step Algorithm:

• Initialize an empty array to store the result.
• Iterate through each element in arr1[].
• For each element in arr1[], check if it exists in arr2[].
• If it does, add it to the result array.

C++ code Implementation.

// C++ code to find intersection of two array (Brute Force)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> intersectionArrays(vector<int>& arr1, vector<int>& arr2) {
    
    vector<int> result;

    for (int num1 : arr1) {
        // for each element of arr1 check if exist in arr2
        if (find(arr2.begin(), arr2.end(), num1) != arr2.end()) {
            result.push_back(num1);
        }
    }
    
    return result;
}


int main() {
    vector<int> arr1 = {4, 9, 5, 1};
    vector<int> arr2 = {9, 4, 9, 8, 4};

    vector<int> result = intersectionArrays(arr1, arr2);

    // Print the intersection array
    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }

    return 0;
}

Output:

4 9

• Time Complexity: The worst-case time complexity is O(n^2) since, in the worst case, each element of arr1 needs to be compared with each element of arr2.

• Space Complexity: O(m), where m is the number of elements in the result array.

Approach 2: Using Sorting.

This approach involves sorting both input arrays (arr1 and arr2). Then, two pointers traverse both arrays simultaneously, identifying common elements.

Step-by-step Algorithm:

• Sort both arrays, arr1[], and arr2[].
• Initialize pointers i and j to traverse arr1[] and arr2[], respectively.
• Compare elements at indices i and j.
• If the elements are equal, add the element to the result and move both pointers forward.
• If the element at arr1[i] is smaller, move the i pointer forward; otherwise, move the j pointer forward.

C++ Code Implementation.

// C++ code to find intersection of two array
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// function to find intersection of arrays
vector<int> intersectionArrays(vector<int>& arr1, vector<int>& arr2) {
    vector<int> result;
    //sorting both the array
    sort(arr1.begin(), arr1.end());
    sort(arr2.begin(), arr2.end());
    
    int i = 0, j = 0;
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] == arr2[j]) {
            result.push_back(arr1[i]);
            i++;
            j++;
        } else if (arr1[i] < arr2[j]) {
            i++;
        } else {
            j++;
        }
    }
    return result;
}



int main() {
    vector<int> arr1 = {4, 9, 5, 1};
    vector<int> arr2 = {9, 4, 9, 8, 4};

    vector<int> result = intersectionArrays(arr1, arr2);

    // Print the intersection array
    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }

    return 0;
}

Output:

4 9

• Time Complexity: O(n log n + m log m), where n and m are the sizes of arr1 and arr2, respectively, accounting for sorting.

• Space Complexity: O(1) as no additional space is required except for pointers and the result array.

Approach 3: Using Hash Set.

In this approach, a hash set is employed to store unique elements from the first array (arr1). The second array (arr2) is then traversed, and common elements are added to the result array.

Step-by-step Algorithm:

• Initialize an empty hash set to store unique elements from arr1[].
• Iterate through arr1[] and add each element to the hash set.
• Initialize an empty array to store the result.
• Iterate through arr2[].
• If an element in arr2[] is present in the hash set, add it to the result array.

C++ code Implementation.

// C++ code to find intersection of two array
// using hash table
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

// function to find intersection of arrays
vector<int> intersectionArrays(vector<int>& arr1, vector<int>& arr2) {
    //adding unique elements of arr1 to hash set
    unordered_set<int> set1(arr1.begin(), arr1.end());
    vector<int> result;
    
    for (int num : arr2) {
        if (set1.count(num)) {
            result.push_back(num);
            // To avoid duplicates in result
            set1.erase(num); 
        }
    }
    
    return result;
}

int main() {
    vector<int> arr1 = {4, 9, 5, 1, 0};
    vector<int> arr2 = {9, 4, 9, 8, 4, 1};

    vector<int> result = intersectionArrays(arr1, arr2);

    // Print the intersection array
    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }

    return 0;
}

Output:

4 9 1

• Time Complexity: O(n + m), where n and m are the sizes of arr1 and arr2, respectively.

• Space Complexity: O(1) as no additional space is required except for pointers and the result array.

All the above approaches have different space and time complexities so you can choose which one is best for you based on your requirement to find a common intersection of two arrays.

Program to Left Rotate an Array by K Places.

Given an integer array arr[] of size n, the task is to rotate the array to the left by K steps, where K is a non-negative number.

Example:

Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}  K = 3
Output: arr[] = {4, 5, 6, 7, 8, 1, 2, 3}

Input: arr[] = {4, 6, 1, 5, 2, -2}  k = 2
Output: arr[] = {1, 5, 2, -2, 4, 6}

There are multiple approaches to rotating an array and here we are going to discuss each of them one by one in detail.

Key Note: When the number of rotations (K) is greater than the size of the array (n) for a left rotation, we can handle it by taking the effective number of rotations, which is K % n. This is because, after every n rotation, the array comes back to its original position. So, rotating by K % n is equivalent to rotating by K. (alert-passed)

Approach 1: Brute Force Approach.

This approach takes a straightforward but less efficient approach. It involves repeatedly shifting the entire array to the left by one position K times. While conceptually simple, this method has a time complexity of O(n * k), making it less suitable for large arrays or a high number of rotations.

Step-by-step algorithm:

• Store the first element in a temporary variable.
• Shift all elements in the array to the left by one position.
• Place the temporary variable at the end of the array.
• Repeat steps 1-3 for K times.

Below is the C++ code implementation of the above approach:

// C++ code to left rotate array by k position 
#include <iostream>
using namespace std;

// function to left rotate an array
void rotateLeftBruteForce(int arr[], int n, int k) {
    for (int i = 0; i < k; ++i) {
        int temp = arr[0];
        for (int j = 1; j < n; ++j) {
            arr[j - 1] = arr[j];
        }
        arr[n - 1] = temp;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;

    rotateLeftBruteForce(arr, n, k);

    // Print the rotated array
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

3 4 5 6 7 1 2

• Time Complexity: O(n * k) where n is the number of elements present in the array and k is the number of position the array need to be rotated.

• Space Complexity: O(1) no extra space is required to solve this problem using the above approach.

Approach 2: Using Extra Space.

In this approach, an auxiliary array is utilized to store the first K elements of the original array. The remaining elements are then shifted to the left in the original array, and the elements from the auxiliary array are placed at the end.

Step-by-step algorithm:

• Create an auxiliary array of size K.
• Copy the first K elements of the original array to the auxiliary array.
• Shift the remaining elements in the original array to the left by K positions.
• Copy the elements from the auxiliary array to the end of the original array.

Below is the C++ code implementation for the above approach:

// C++ code to left rotate an array using extra space
#include <iostream>
using namespace std;

void rotateLeftExtraArray(int arr[], int n, int k) {
    // Check for the case where k is greater than n
    k = k % n;

    // Create an auxiliary array
    int temp[k];

    // Copy the first k elements to the auxiliary array
    for (int i = 0; i < k; ++i) {
        temp[i] = arr[i];
    }

    // Shift the remaining elements 

    // in the original array to the left
    for (int i = k; i < n; ++i) {
        arr[i - k] = arr[i];
    }

    // Copy the elements from the auxiliary array 

    // to the end of the original array
    for (int i = 0; i < k; ++i) {
        arr[n - k + i] = temp[i];
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    rotateLeftExtraArray(arr, n, k);

    // Print the rotated array
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

4 5 6 7 1 2 3

• Time Complexity: O(n) where n is the number of elements present in the array and k is the number of position the array need to be rotated.

• Space Complexity: O(k) k is the size of an auxiliary array that is used in the above algorithm to rotate the array.

Approach 3: Reversal Algorithm.

The Reversal Algorithm reverses specific segments of the array to achieve rotation. First, it reverses the first K elements, then the remaining elements, and finally the entire array. 

Step-by-step algorithm:

• Reverse the first K elements of the given array.
• Reverse the remaining elements of the given array.
• Reverse the entire array.

Illustration:

Below is the C++ code implementation for the above approach:

// C++ code to left rotate an array using reversal method
#include <iostream>
using namespace std;

// function to reverse array
void reverseArray(int arr[], int start, int end) {
    while (start < end) {
        std::swap(arr[start], arr[end]);
        ++start;
        --end;
    }
}

// function to left rotate array
void rotateLeftReversal(int arr[], int n, int k) {
    // Check for the case where k is greater than n
    k = k % n;

    // Reverse the first k elements
    reverseArray(arr, 0, k - 1);

    // Reverse the remaining elements
    reverseArray(arr, k, n - 1);

    // Reverse the entire array
    reverseArray(arr, 0, n - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    rotateLeftReversal(arr, n, k);

    // Print the rotated array
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

4 5 6 7 1 2 3

• Time Complexity: O(n) where n is the number of elements present in the array and k is the number of position the array need to be rotated.

• Space Complexity: O(1) as no extra space is required to resolve the problem.

Approach 4: Juggling Algorithm.

The Juggling Algorithm is an optimization over the reversal method. It uses the concept of finding the greatest common divisor (gcd) of n and k. It then iterates through sets of elements that need to be rotated together, reducing the number of swaps needed.

Step-by-step algorithm:

• Find the greatest common divisor (gcd) of n and k.
• Iterate through each set of elements that need to be rotated together.
• Use temporary variables to swap elements within each set.

Below is the C++ code implementation for the above approach:

// C++ code to rotate array using juggling algorithm
#include <iostream>
using namespace std;

// function to find gcd
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// function to left rotate array
void rotateLeftJuggling(int arr[], int n, int k) {
    // Check for the case where k is greater than n
    k = k % n;

    // Find the greatest common divisor (gcd) of n and k
    int sets = gcd(n, k);

    for (int i = 0; i < sets; ++i) {
        int temp = arr[i];
        int j = i;

        while (true) {
            int d = (j + k) % n;
            if (d == i) {
                break;
            }
            arr[j] = arr[d];
            j = d;
        }

        arr[j] = temp;
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;

    rotateLeftJuggling(arr, n, k);

    // Print the rotated array
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

4 5 6 7 1 2 3

• Time Complexity: O(n) where n is the number of elements present in the array and k is the number of position the array need to be rotated.

• Space Complexity: O(1) as no extra space is required.

These are the few algorithms to left rotate an array by K position and you can choose one which is best for your requirement.

Constructor and Destructor in C++.

Constructor and Destructor in C++ are the special member functions of the class and they are essential components of Object Oriented Programming. Constructors are special functions within a class that initialize the object when it is created, providing default or custom values to its attributes. On the other hand, destructors are used to clean up resources allocated by the object during its lifetime, and they are automatically invoked when the object goes out of scope or is explicitly deleted.

What is a Constructor in C++?

A constructor in C++ is a special member function of a class that is automatically invoked when an object of that class is created. Its primary purpose is to initialize the object's attributes or perform any necessary setup. Constructors have the same name as the class and do not have a return type. 

There are many types of constructors available in C++. When an object is instantiated, the appropriate constructor is automatically called, ensuring that the object is properly initialized before it is used. Constructors play a crucial role in object-oriented programming by establishing the initial state of objects.

How many types of constructors in C++?

There are basically four types of constructors present in C++ and these are:

• Default Constructor.
• Parameterized Constructor.
• Copy Constructor.
• Dynamic Constructor.

Let's discuss each of them in detail one by one,

Default Constructor.

A default constructor in C++ is a constructor that takes no parameters. It is automatically generated by the compiler if no constructor is explicitly defined in the class. It is called when an object is created with no arguments.

Syntax:

class ClassName {
public:
    ClassName() {
        // Constructor code
    }
};

Example Code for Default Constructor:

// C++ code implementation for default constructor
#include <iostream>
using namespace std;

class MyClass {
private:
    int rollNo;
    string name;

public:
    // Default Constructor
    MyClass() {
        std::cout << "Default Constructor Called" << std::endl;
        rollNo = 0;
        name = "NULL";
    }

    void display(){
        cout << "Student Name: " << name << endl;
        cout << "Roll No: " << rollNo << endl;
    }
};

int main() {
    // Creating an object invokes the default constructor
    MyClass obj;  

    obj.display();
    return 0;
}

Output:

Default Constructor Called
Student Name: NULL
Roll No: 0

In the above example, we created a class MyClass with a default constructor to initialize the initial values to data members of the class, and the default constructor is called as soon as we create the object of that class obj. 

Note: It's important to explicitly define a default constructor when custom initialization is required or when other constructors are defined in the class. (alert-passed)

Parameterized Constructor.

A parameterized constructor in C++ is a constructor that accepts parameters during its invocation. It allows you to initialize the object with specific values based on the provided arguments. 

Syntax:

class ClassName {
public:
    ClassName(type1 param1, type2 param2, ...) {
        // Constructor code
    }
};

Example Code for Parameterized Constructor:

// C++ code implementation for Parameterized constructor
#include <iostream>
using namespace std;

class Car {
private:
    string brand;
    int year;

public:
    // Parameterized Constructor
    Car(string b, int y) {
        cout << "Parameterized Constructor Called" << endl;
        brand = b;
        year = y;
    }

    void display() {
        cout << "Brand: " << brand << ", Year: " << year << endl;
    }
};

int main() {
    // Creating an object using the parameterized constructor
    Car myCar("Toyota", 2022);
    myCar.display();  
    return 0;
}

Output:

Parameterized Constructor Called
Brand: Toyota, Year: 2022

In the above example, the parameterized constructor takes parameters (in this case, a string and an integer) during its declaration. The constructor is called when an object is created, allowing custom initialization based on the provided arguments.

Copy Constructor.

A copy constructor in C++ is a special type of constructor that is used to create a new object as a copy of an existing object of the same class. It is invoked when an object is passed by value or returned by value.

Note: If a copy constructor is not explicitly defined, the compiler generates a default copy constructor. (alert-success)

Syntax:

class ClassName {
public:
    // Copy Constructor
    ClassName(const ClassName& obj) {
        // Constructor code
    }
};

Example Code for Copy Constructor:

// C++ code implementation for Copy constructor
#include <iostream>
using namespace std;

class Student {
private:
    string name;
    int age;

public:
    // Parameterized Constructor
    Student(string n, int a) : name(n), age(a) {
        cout << "Parameterized Constructor Called" << endl;
    }

    // Copy Constructor
    Student(const Student& obj) : name(obj.name), age(obj.age) {
        cout << "Copy Constructor Called" << endl;
    }

    void display() {
        cout << "Name: " << name << ", Age: " << age << endl;
    }
};

int main() {
    // Creating an object using the parameterized constructor
    Student originalStudent("John", 20);
    originalStudent.display();  

    // Creating a new object using the copy constructor
    Student copiedStudent = originalStudent;
    copiedStudent.display();  
    
    return 0;
}

Output:

Name: John, Age: 20
Copy Constructor Called
Name: John, Age: 20

In the above example, the copy constructor takes a reference to an object of the same class (const ClassName& obj) as its parameter. It initializes the members of the new object with the values of the corresponding members of the existing object.

Dynamic Constructor.

In C++, a dynamic constructor is not a distinct type of constructor. Constructors are typically classified based on their parameters and use cases, such as default constructors, parameterized constructors, and copy constructors. However, there might be a misunderstanding or miscommunication about the term "dynamic constructor."

If you are referring to dynamic memory allocation within a constructor (e.g., using new), this is a common practice in C++ but doesn't give rise to a separate category of a constructor. 

What is a Destructor in C++?

A destructor in C++ is a special member function of a class that is executed whenever an object of the class goes out of scope or is explicitly deleted. It is used to release resources or perform cleanup operations associated with the object before it is destroyed.

Syntax:

class ClassName {
public:
    // Constructor(s)
    ClassName(); // Default constructor
    ClassName(parameters); // Parameterized constructor

    // Destructor
    ~ClassName(); 
};

Key points about Destructor:

• A destructor has the same name as the class but is prefixed with a tilde (~).
• Unlike constructors, which can be overloaded, a class can have only one destructor.
• The destructor is automatically invoked when an object goes out of scope or is explicitly deleted.
• It is used for releasing resources, closing files, releasing memory, or performing any cleanup necessary before the object is destroyed.

Example Code for Destructor in C++:

// C++ code implementation for Destructor
#include <iostream>
using namespace std;

class MyClass {
public:
    // Constructor
    MyClass() {
        std::cout << "Constructor Called" << std::endl;
    }

    // Destructor
    ~MyClass() {
        std::cout << "Destructor Called" << std::endl;
    }
};

int main() {
    // Creating an object
    MyClass obj; 

    // Object goes out of scope, destructor is called
    return 0;
}

Output:

Constructor Called
Destructor Called

Note: In the example, the destructor prints a message for demonstration purposes. In real-world scenarios, destructors are often used to deallocate memory, close files, or release other resources.(alert-passed)

 (getButton) #text=(Access Specifiers in C++) #icon=(link) #color=(#2339bd)