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)

String Member Functions in C++

We covered the fundamentals of String Class in C++ in our previous post. In this post, we are going to cover the several operations and functionalities that we can perform on the String type. There are several member functions that are available in string class in C++ which is veryful for solving string related coding problems. 

Here we are going to discuss all the string member functions available in C++ programming language with real example and code implementation.

String empty() function in C++.

String Function	Definition
empty()	This function is used to check if a string is empty or not. It returns 1 if a string is empty else returns 0 if a string is not empty.

Example C++ Code:

/*C++ program to show the working of
empty() function
*/
#include<iostream>
#include<string>
using namespace std;

int main(){
    
    string str;
    //taking input from user
    cout<<"Enter a string: ";
    getline(cin, str);
    //checking string is empty or not
    if(!str.empty()){
        cout<<"The string is: "<<str<<endl;
    }
    else{
        cout<<"The string is empty!"<<endl;
    }
    
    return 0;
}

Output:

Enter a string: 
The string is empty!
Enter a string: Algolesson
The string is: Algolesson

In the output of the above code, you can see that when I enter nothing as an input, the empty() function checks the string and executes the else part saying, "The string is empty!". You have also noticed one getline() function that takes input from the user.

String Modifier functions in C++.

String Function	Definition
push_back()	This function is used to add a character at the end of the string.
pop_back()	This function is used to delete the last character from the string.
insert()	This function is used to insert additional characters into the string.
erase()	This function is used to remove the part of the string which reduce the size of the string.

Example C++ Code:

/*C++ program to show the working of erase()
insert(), push_back() and pop_back() function
*/
#include<iostream>
#include<string>
using namespace std;

int main(){
    
    string str;
    //taking input from the user
    cout<<"Enter a string: ";
    getline(cin, str);
    
    cout<<"The string is: "<<str<<endl;
    //adding a char at the end of the string
    str.push_back('s');
    cout<<"String after push_back() operation: "<<str<<endl;
    //removing a char from the end of the string
    str.pop_back();
    cout<<"String after pop_back() operation: "<<str<<endl;

    string str1 = "Rose is a ";
    str.insert(0, str1);
    cout<<"String after insert operation: "<<str<<endl;

    str.erase(10, 10);
    cout<<"String after erase operation: "<<str<<endl;
    return 0;
}

Output:

Enter a string: Beautiful Flower
The string is: Beautiful Flower
String after push_back() operation: Beautiful Flowers
String after pop_back() operation: Beautiful Flower

String after insert operation: Rose is a Beautiful Flower

String after erase operation: Rose is a Flower

If you are already working with string then you probably know the functionality of getline() function. In the above code, push_back('s') adds one s character at the end of our string and the pop_back() function removes that end 's' character.

String Capacity functions in C++. 

String Function	Definition
capacity()	This function is used to return the capacity allocated to the string which can be equal to more than the length of the string.
length()	This function is used to check the length of the string.
resize()	This function is used to change the size of the current string. The size of the string can be increased or decreased based on demand.
shrink_to_fit()	This function is used to decrease the capacity of the string to fit its size. It makes string capacity equal to string size.
size()	This function is used to find the length of the string which also indicates the number of characters present in the string.

• The size() functional and length() function return the same value always.

Example C++ Code:

/*C++ program to show the working of resize(),
capacity() and shrink_to_fit() function
*/
#include<iostream>
#include<string>
using namespace std;

int main(){
    
    string str;
    //taking input from user
    cout<<"Enter a string: ";
    getline(cin, str);
    
    cout<<"The string is: "<<str<<endl;

    str.resize(7);
    cout<<"String after resize operation: "<<str<<endl;

    cout<<"The capacity of the string is: "<<str.capacity()<<endl;

    cout<<"The length of the string is: "<<str.length()<<endl;

    str.shrink_to_fit();
    cout<<"The capacity of the string after shrink: "<<str.capacity()<<endl;

    cout<<"The size of the string is: "<<str.size()<<endl;
    return 0;
}

Output:

Enter a string: Welcome to Algolesson
The string is: Welcome to Algolesson
String after resize operation: Welcome
The capacity of the string is: 30
The length of the string is: 7
The capacity of the string after shrink: 15

The size of the string is: 7

In the above, code you can see that number of characters present in the input string was 21 and after resizing the string to 7 it contains only 7 characters but the capacity of the string was still 30 and even tho the length of the string showing is 7 so after performing shrink operation to free unwanted memory the capacity reduced to 15. 

String Iterator Functions in C++.

String Function	Definition
begin()	This function is used to return an iterator to the beginning of the string.
end()	This function is used to return an iterator to the end of the string.
rbegin()	This function is used to return a reverse iterator pointing at the end of the string.
rend()	This function is used to return a reverse iterator pointing at the beginning of the string.

Example C++ Code:

/*C++ program to show the working of begin(), end()
rbegin() and rend() function
*/
#include<iostream>
#include<string>
using namespace std;

int main(){
    
    string str = "Algolesson";
    
    std::string::iterator it;

    cout<<"Print String using forward iterator: ";
    for(it = str.begin(); it != str.end(); it++)
       cout<<*it;
    cout<<endl;

    std::string::reverse_iterator rit;

    cout<<"Print String using reverse iterator: ";
    for(rit = str.rbegin(); rit != str.rend(); rit++)
       cout<<*rit;   
       
    return 0;
}

Output:

Print String using forward iterator: Algolesson
Print String using reverse iterator: nosseloglA

In the above code, when we use the reverse iterator to print our string then it prints the string in reverse order because begin() points to the end of the string to it start printing in reverse order.

String Operation Functions in C++.

String Function	Definition
copy()	This function is used to copy a sequence of characters from the string. This function returns a char array and the function required three arguments, the name of the char array, the length of the string to be copied, and the starting position of copying.
find()	This function is used to find content in the string. It can contain two arguments, First argument is the string to be searched for. Second argument is the starting index at which the search is going to start.
substr()	This function is used to generate a substring of the string. It contain two argument, First argument is the position of first character to be copied as a substring. Second argument tell us about the length of the substring.
compare()	This function is used to compare two strings and return 0 if both are equal.

Example C++ Code:

/*C++ program to show the working of copy(), find()
substr() and compare() function
*/
#include<bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;

int main(){

  string str = "Coding is Fun";
  string str1 = "Programming is Fun Coding is Fun";
  string str2 = "Fun";
  
  //char array of size 20
  char copystr[20];
  int length = str1.copy(copystr, 11, 0);
  copystr[length] = '\0';
  cout<<"The copied character array is: "<<copystr<<endl;

  int found = str1.find(str2);
  cout<<"The First occurrence of str2 at: "<<found<<endl;

  found = str1.find(str2, found+1);
  cout<<"The Second occurrence of str2 at: "<<found<<endl;

  string str3 = str1.substr(19, 6);
  cout<<"The First substring is: "<<str3<<endl;

  str3 = str1.substr(19);
  cout<<"The Second substring is: "<<str3<<endl;

  if(str.compare(str3) == 0)
    cout<<"Both strings are equal."<<endl;
     
  return 0;
}

Output:

The copied character array is: Programming
The first occurrence of str2 at: 15
The Second occurrence of str2 at: 29
The First substring is: Coding
The Second substring is: Coding is Fun
Both strings are equal.

In the above code, the copy() function return the character array and with null character at the end so we need to append it sepeararately or it might cause unexpected error. The substr() function help to capture substring and usually required two argument (starting position and size of substring) but if you don't provide the size of substring then it will capture from starting position till end of the string.

I hope you found this article useful, please share your feedback in the comment section below so we can work on them to provide you the best content.