Count number of elements smaller than current number.

Given an array num of size n, for each element of num count the number of elements of the array that are smaller than the current element. It means for each element num[i] you need to count the number of elements such that num[j] < num[i] and j != i. Return the counts in an array.

Example:

Example 1:
Input: num[] = {3, 2, 5, 1, 7};
Output: {2, 1, 3, 0, 4}

Explanation: 
Number of Elements smaller than num[0] = 3 are (1 and 2) = 2 
Number of Elements smaller than num[1] = 2 are (1) = 1
Number of Elements smaller than num[2] = 5 are (1, 2 and 3) = 3
Number of Elements smaller than num[3] = 1 are () = 0
Number of Elements smaller than num[4] = 7 are (1, 2, 3 and 5) = 4

Example 2:
Input: num[] = {3, 3, 3, 3}
Output: {0, 0, 0, 0}

Example 3:
Input: num[] = {3, 2, 2, 5, 1, 7}
Output: {3, 1, 1, 4, 0, 5}

The question is very simple, you just have to get the counts of smaller elements for each and store them one by one in an array or vector and return them as your output. This question can be solved by multiple approaches let's discuss them here.

Note: We are using a C++ vector in our solution instead of an array because vectors are dynamic in nature and provide more functionality. (alert-passed)  

Approach 1: Brute Force Solution.

You can run two nested loops, the outer loop will pick elements of the array one by one, and the inner loop will traverse the whole array each time to check and count the elements that satisfy the given condition. Each time the inner loop terminates store the count value into a new resulting array and return this array at the end. 

 

C++ Solution code:

/*C++ program for how many number of elements smaller
 than current number.*/
#include<iostream>
#include<vector>
using namespace std;

vector<int> smallerNumber(vector<int> &num){
    vector<int> ans;
    int count;

    for(int i = 0; i < num.size(); i++){
        count = 0;
        for(int j = 0; j < num.size(); j++){
            if(num[i] > num[j])
               count++;
        }
        ans.push_back(count);
    }
    return ans;
}

int main(){
    vector<int> num = {3, 2, 2, 5, 1, 7};

    vector<int> result = smallerNumber(num);

    for(int i = 0; i < result.size(); i++)
       cout<<result[i]<<" ";

    return 0;   
}

Output:

3 1 1 4 0 5

• Time Complexity: Running two nested loops from 0 to n will take n x n units of time so the time complexity will be O(n^2).
• Space Complexity: No extra space is required to perform any operation except the answer vector that is used to store the counts but we cannot consider this for calculating space complexity so overall space complexity will be O(1).

Approach 2: Using Hash Map and Sorting.

The above approach is solving the problem in O(n^2) time complexity but we can optimize the solution and can bring it to O(nlogn) time complexity by following the below algorithm.

Given num = [3, 2, 2, 5, 1, 7]

Step 1: Make a copy of the given array and sort it in ascending order.

copy = [1, 2, 2, 3, 5, 7]

Step 2: Store the values in a hash map corresponding to their index in reverse order. A map can store only unique values and storing values in reverse will help you to get the count of smaller values by their index.

mp[copy[5]] = mp[7] = 5
mp[copy[4]] = mp[5] = 4
mp[copy[3]] = mp[3] = 3
mp[copy[2]] = mp[2] = 1(overwritten 2 to 1)  
mp[copy[0]] = mp[1] = 0

Step 3: Store the values back in the num array.

num[0] = mp[num[0]] = mp[3] = 3
num[1] = mp[num[1]] = mp[2] = 1
num[2] = mp[num[2]] = mp[2] = 1
num[3] = mp[num[3]] = mp[5] = 4
num[4] = mp[num[4]] = mp[1] = 0
num[5] = mp[num[5]] = mp[7] = 5

Step 4: Return the num array as our answer.

num = [3, 1, 1, 4, 0, 5]

C++ Solution code:

/*C++ Optimized program for how many number of elements 
smaller than current number.*/
#include<bits/stdc++.h>
using namespace std;

vector<int> smallerNumber(vector<int> &num){
    unordered_map<int, int> mp;

    //make a copy vector
    vector<int> copy = num;
    //sort the copy vector in ascending order
    sort(copy.begin(), copy.end());

    //store elements corresponding to their index
    for(int i = num.size() - 1; i >= 0; i--){
        mp[copy[i]] = i;
    }
    
    //store map value back to num array
    for(int i = 0; i < num.size(); i++){
        num[i] = mp[num[i]];
    }
    return num;
}

int main(){
    vector<int> num = {3, 2, 2, 5, 1, 7};

    vector<int> result = smallerNumber(num);

    for(int i = 0; i < result.size(); i++)
       cout<<result[i]<<" ";

    return 0;   
}

Output:

3 1 1 4 0 5

• Time Complexity: Sorting the copied array will take O(nlogn) time, and running two separate loops for n elements will take 2O(n) time so the overall time complexity of our solution is O(nlogn).
• Space Complexity: As we are using a new copy vector and unordered map for storing the element so overall space complexity is O(n). 

How To Pass Array to Function in C++.

As we know that an array is a collection same kind of data in a contiguous memory location but can we pass the array data as an argument to a function? The answer to this question is no. We cannot pass the entire array as an argument to a function but we can pass a pointer to an array. 

We have totally different methods for passing a one-dimensional and two-dimensional array to a function in C++. Let's discuss both of them one by one:

Passing One-Dimensional Array to Function.

We have passed the name of our array without an index to a function and the name of the array behaves like a pointer folding the address of the first element of the array. Any changes made in the array inside the function will directly affect the elements of the main array. 

C++ Example Code:

//C++ Example to show ways of Passing Array to Function
#include<iostream>
using namespace std;

//Formal parameter as unsized array
void funType1(int arr[], int n){

	int size = sizeof(arr)/sizeof(arr[0]);
	cout<<"\nSize of array inside fun1: "<<size<<endl;

	arr[2] = 10;  
	cout<<"Array Elements in fun1: ";
	for(int i = 0; i < n; i++)
	  cout<<arr[i]<<" ";
}

//Formal parameter as a pointer
void funType2(int *arr, int n){

	int size = sizeof(arr)/sizeof(arr[0]);
	cout<<"Size of array inside fun2: "<<size<<endl;

	arr[n-1] = 23; 
	cout<<"Array Elements in fun2: ";
	for(int i = 0; i < n; i++)
	  cout<<arr[i]<<" "; 
}

int main(){

	int arr[] = {3, 4, 5, 7, 8, 9};
	//size of array
	int n = sizeof(arr)/sizeof(arr[0]);
	cout<<"Size of given array: "<<n<<endl;

	cout<<"Array Elements: ";
	for(int i = 0; i < n; i++)
	  cout<<arr[i]<<" ";
        
        //function 1 call
	funType1(arr, n);
	cout<<endl;

        //function 2 call
	funType2(arr, n);

	return 0;
}

Output:

Size of given array: 6
Array Elements: 3 4 5 7 8 9
Size of array inside fun1: 2
Array Elements in fun1: 3 4 10 7 8 9
Size of array inside fun2: 2
Array Elements in fun2: 3 4 10 7 8 23

We have two ways of writing an array into a function as an argument, 

• The first is passing an unsized array as a parameter. (syntax: fun(int arr[])) 
• The second is passing as a pointer. (syntax: fun(int *arr))

Both hold the address of only the first element of the array.

We cannot calculate the size of the array inside the function we must have to pass the array size as a parameter. 

Passing Two-Dimensional Array to Function.

To pass a 2D array (also known as a matrix) to a function we must have to pass the second dimension value to the function were passing the first dimension value is totally optional. 

Syntax: fun(int arr[][m])

C++ Example Code:

//C++ Example code for passing 2D array to function
#include<iostream>
using namespace std;

//Passing matrix to a function
void fun2DArray(int arr[][3], int r, int c){
	cout<<"Elements of 2D Array: "<<endl;
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			cout<<arr[i][j]<<" ";
		}
		cout<<endl;
	}
}
int main(){
	
	int arr[][3] = {{2, 3, 7},{9, 5, 1},{4, 6, 2}};
	
	int row = sizeof(arr)/sizeof(arr[0]);
	int col = sizeof(arr[0])/sizeof(arr[0][0]);

	fun2DArray(arr, row, col);

	return 0;
}

Output:

Elements of 2D Array: 
2 3 7
9 5 1
4 6 2

In the above code, you can also check how we can calculate the number of rows and columns of a 2D Array using the sizeof() operator.

Next:

(getButton) #text=(Difference between Subarrays, Subsequences and Subsets.) #icon=(link) #color=(#2339bd)

Vector Type STL in C++

Vectors are sequence containers that work the same as variable-size Arrays. It is a kind of STL (Standard Template Library) based on a class template that can provide standard functionality like a Dynamic Array. Similarly, like an array, a vector can be of any type like a character array, integer array, boolean array, string array, etc. 

A Template is not a class or function it is like a blueprint or a guideline for the compiler to use the template to create a specific class or function. We specify which class to instantiate by supplying additional information depending on the template in our case we will specify the vector data type in between two angle brackets after the template name.

• syntax: vector<datatype> vector_name;
• example: vector<int> myvec;(alert-success)

In a vector, elements are in contiguous memory locations, and when we insert a value in a vector stored at the end. Removing or inserting values into a vector takes a constant amount of time and their size grows dynamically as their storage is handled by a container. We need to include a specific <vector> header file in our C++ program to use all the functionality of vector. 

Vector Functions.

There is a list of member functions available in the vector header file that we can directly use for solving our coding problems. Let's understand them one by one.

Iterator member functions:

Member Function	Definition
begin()	This function returns an iterator pointer pointing to the first element of the vector.
end()	This function returns an iterator pointer pointing to the last element of the vector.
rbegin()	This function returns a reverse iterator pointer pointing to the last element of the vector. It follows a reverse order and moves from the last element toward the first.
rend()	This function returns a reverse iterator pointer pointing to the first element of the vector. It follows a reverse order and moves from the first element toward the last.
cbegin()	This function returns a const_iterator pointing to the first element of the vector container. This const_iterator is used to point to a const value.
cend()	This function returns a const_iterator pointing to the last element of the vector container. This const_iterator is used to point to a const value.
crbegin()	This function returns a const_reverse_iterator pointing to the last element of the vector container.
crend()	This function returns a const_reverse_iterator pointing to the first element of the vector container.

C++ Example Code:

//C++ Program to show iterator function of vector STL
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //declaration of integer type vector
    vector<int> myVec;

    //inserting elements in vector
    for(int i = 0; i < 6; i++)
       myVec.push_back(i+2);

    cout<<"Printing values using begin() and end() fun: ";
    for(auto it = myVec.begin(); it != myVec.end(); it++)
       cout<<*it<<" ";  

    cout<<"\nPrinting values using rbegin() and rend(): ";
    for(auto it = myVec.rbegin(); it != myVec.rend(); it++)
       cout<<*it<<" ";

    cout<<"\nPrinting values using cbegin() and cend(): ";
    for(auto it = myVec.cbegin(); it != myVec.cend(); it++)
       cout<<*it<<" ";  

    cout<<"\nPrinting values using crbegin() and crend(): ";
    for(auto it = myVec.crbegin(); it != myVec.crend(); it++)
       cout<<*it<<" ";   

    return 0;        
}

Output:

Printing values using begin() and end() fun: 2 3 4 5 6 7
Printing values using rbegin() and rend(): 7 6 5 4 3 2
Printing values using cbegin() and cend(): 2 3 4 5 6 7
Printing values using crbegin() and crend(): 7 6 5 4 3 2

Vector Functions to Check Capacity.

Member Function	Definition
size()	This function returns the size of the vector or we can say it returns a number of elements present in the vector.
capacity()	This function returns the current allocated storage space to the vector. This capacity might not be equal to the size of the vector.
shrink_to_fit()	This function decreases the current capacity of the vector container and makes it equal to the size.
resize(n)	This function changes the vector's current size to make it fit for n elements.
reserve()	This function requests that the vector capacity be at least enough for n elements only when the current capacity is not enough for n elements.
empty()	This function is used to check if the vector is empty or not or if the size is equal to 0 then it returns true else returns false.
max_size()	This function gives us an idea about the maximum number of elements the vector can hold.

C++ Example Code:

//C++ Program to show capacity function of vector STL
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //declaration of integer type vector
    vector<int> myVec;

    //inserting elements in vector
    for(int i = 0; i < 6; i++)
       myVec.push_back(i+2);

    if(!myVec.empty()){
        cout<<"Size: "<<myVec.size()<<endl;
        cout<<"Capacity: "<<myVec.capacity()<<endl;
        cout<<"Maximum Size: "<<myVec.max_size()<<endl;

        myVec.shrink_to_fit();
        cout<<"Capacity after shrinking: "<<myVec.capacity()<<endl;
    }
    else{
        cout<<"Vector is empty!!!"<<endl;
    } 

    cout<<"Elements present in the vector: ";
    for(auto it = myVec.begin(); it != myVec.end(); it++)
       cout<<*it<<" ";  

    return 0;        
}

Output:

Size: 6
Capacity: 8
Maximum Size: 230584300921363951
Capacity after shrinking: 6
Elements present in the vector: 2 3 4 5 6 7

Element Access member functions:

Member Function	Definition
operator[i]	This function returns a reference to the element at the position mentioned in the square bracket in the vector.
at(i)	This function works the same as the previous one and returns a reference to the element present at position i in the vector.
front()	This function returns a reference to the first element of the vector.
back()	This function returns a reference to the first element of the vector.
data()	This function returns a direct pointer to the memory array used internally by the vector to store its owned elements.

C++ Example Code:

//C++ Program to show Element access function of vector STL
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //declaration of integer type vector
    vector<int> myVec;

    //inserting elements in vector
    for(int i = 0; i < 6; i++)
       myVec.push_back(i+2);

    cout<<"Elements present in the vector: ";
    for(auto it = myVec.begin(); it != myVec.end(); it++)
       cout<<*it<<" ";  

    cout<<"\nElement at position myVec[3]: "<<myVec[3]<<endl;
    myVec[3] = 10;
    cout<<"Element at position myVec[3]: "<<myVec.at(3)<<endl;

    cout<<"First element of vector: "<<myVec.front()<<endl;
    cout<<"Last element of vector: "<<myVec.back()<<endl;

    int *p = myVec.data();
    cout<<"First element of vector: "<<*p;

    return 0;        
}

Output:

Elements present in the vector: 2 3 4 5 6 7
Element at position myVec[3]: 5
Element at position myVec[3]: 10
First element of vector: 2
Last element of vector: 7
First element of vector: 2

Vector Modifier member functions.

Member Function	Definition
push_back()	This function is used to insert or add an element at the end of the vector.
pop_back()	This function is used to delete an element from the end of the vector.
insert()	This function is used to insert an element before the element at the specified position.
assign()	This function is used to assign new values to the vector elements by replacing the old values.
erase()	This function is used to remove a single element or a range of elements from a vector.
swap()	This function is used to swap the values of one vector with the values of other vectors of the same type. The size of both vectors might not be the same.
clear()	This function is used to remove all the elements of the vector and empty it.
emplace()	This function is used to insert a new element at a specific position and extend the size of the vector by one.
emplace_back()	This function is used to insert a new element at the end position and effectively extend the size of the vector by one.

C++ Example Code:

//C++ Program to show Element access function of vector STL
#include<iostream>
#include<vector>
using namespace std;

int main(){
    //declaration of integer type vector
    vector<int> myVec;

    //inserting elements in vector
    for(int i = 0; i < 6; i++)
       myVec.push_back(i+2);

    cout<<"Elements present in the vector: ";
    for(auto it = myVec.begin(); it != myVec.end(); it++)
       cout<<*it<<" ";  

    myVec.push_back(50);
    cout<<"\nLast Element after push_back: "<<myVec.back()<<endl;
    //removing the last element
    myVec.pop_back();
    cout<<"Last Element after pop_back: "<<myVec.back()<<endl;

    //inserting element at pos 4
    myVec.insert(myVec.begin()+3, 35);
    cout<<"Element at position 4: "<<myVec[4]<<endl;
    
    cout<<"Size of vector before emplace: "<<myVec.size()<<endl;
    myVec.emplace(myVec.begin()+4, 55);
    cout<<"Size of vector after emplace: "<<myVec.size()<<endl;

    myVec.clear();
    cout<<"Size of vector after clear: "<<myVec.size()<<endl;

    return 0;        
}

Output:

Elements present in the vector: 2 3 4 5 6 7
Last Element after push_back: 50
Last Element after pop_back: 7
Element at position 4: 5
Size of vector before emplace: 7
Size of vector after emplace: 8
Size of vector after clear: 0

Various operations that we perform on the vector has different time complexity like,

• Accessing any random element takes a constant amount of time O(1).
• Inserting or removing elements takes a linear amount of time O(n) except for the last element which takes a constant amount of time O(1).
• Resizing the vector size in an operation like insert or emplace takes a linear amount of time O(n). 

Next:

(getButton) #text=(Stack STL Container in C++) #icon=(link) #color=(#2339bd)

C++ Program to Make a Calculator using Switch Case.

In this post, we are going to understand how to write simple calculator program in C++ programming language using switch and break statement. 

Our calculator can perform operation like addition, substraction, multiplication and division. It is going to take two input value from the user and the arthematic operator as a single character to perform that particular operation of the input values. 

C++ Example Code for Calculator using Switch statement. 

//C++ Code to make calculator using switch statement
#include<iostream>
using namespace std;

int main(){

    float value1, value2, result;
    char opt;

    cout<<"Enter two values: ";
    cin>>value1>>value2;
    cout<<"Enter the operator: ";
    cin>>opt;

    switch (opt)
    {
    case '+':
        result = value1 + value2;
        cout<<value1<<" + "<<value2<<" = "<<result<<endl;
        break;
    case '-':
        result = value1 - value2;
        cout<<value1<<" - "<<value2<<" = "<<result<<endl;
        break;
    case '*':
        result = value1 * value2;
        cout<<value1<<" * "<<value2<<" = "<<result<<endl;
        break; 
    case '/':
        result = value1 / value2;
        cout<<value1<<" / "<<value2<<" = "<<result<<endl;
        break;       
    default:
        cout<<"Operator not found !!!"<<endl;
        break;
    }
    return 0;
}

Output:

Enter two values: 56 4
Enter the operator: /
56 / 4 = 14

In the above program, we use switch case to check which kind of operator user in providing as an input and based on the correct match of switch we are executing the piece of code written in that particular case. 

Once the operation is performed and it reach the break statement we come out of switch case statements and end the code execution. If any chance we enter any wrong and invalid operator then the default section of switch case will execute. 

Next:

(getButton) #text=(C++ Program to Count Vowels in a String) #icon=(link) #color=(#2339bd)

Concatenate Two Strings and Literals in C++.

Concatenation is a process of linking two more strings together in a chain-like structure to form a bigger string. There are multiple ways of concatenating strings and here we are going to discuss all of them one by one with C++ example code.

In C++, we work with two different kinds of strings one is a C-type string which is also known as Character Array and another is a String Class and we have different methods to concatenate these strings. If you are not familiar with the difference between Character Array and String Class then you can check out our post Character Array Vs String Class in C++. 

Concatenate String Class Objects.

Using + operator: 

We can concatenate two strings easily just by using the simple '+' operator between two strings and it will return us a single concatenated string. 

C++ Example Code:

//C++ example program Concatenation two string
#include<iostream>
#include<string>
using namespace std;

int main(){
  
  string leftstr = "Welcome to ";
  string rightstr = "AlgoLesson";

  //concatenation
  string resultstr = leftstr + rightstr;
  cout<<resultstr<<endl;
  //leftstr = leftstr + rightstr
  leftstr += rightstr;
  cout<<leftstr<<endl;

  return 0;
}

Output:

Welcome to AlgoLesson
Welcome to AlgoLesson

In the above code, we have concatenated two string variables together using the plus operator (+) but when we try to concatenate a string with literals then we need to make sure that at least one operand must be of string type. Let's understand this point with the below example.

string str1 = "Hello";
string str2 = "World";

//OK concatenate successfully
string str3 = str1 + " AlgoLesson " + str2; 

//Error - cannot add two string literals
string str4 = "Wrong" + "Concatenation"; 

//OK - Code execute from left to right 
string str5 = str1 + " Wrong" + " Concatenation"; 

//Error - One side of + operator must be a string type.
string str5 = "Wrong" + " Concatenation " + str1; 

From the above example, we can understand that we cannot directly concatenate two string literals using the + operator. There must be a string one-string type operand at any one side of the + operator.  

Using append() string function:

We have one append() string member function that is also used to add the second string at the end of the first string and store the concatenated string into the first string. 

C++ Example Code:

//C++ program Concatenation two string using append()
#include<iostream>
#include<string>
using namespace std;

int main(){

  string first = "Hello";
  string second = "World";

  first.append(second);

  cout<<first<<endl;
  
  return 0;
}

Output:

HelloWorld

Concatenation C-type string (Character Array).

In C-type string, we have strcat() function that is available inside <string> header file in C++ programming language that appends one string at the end of another string. This function takes two arguments let's say str1 and str2 and then it copies all the character of str2 and add them at the end of str1.

syntax: strcat(str1, str2);

C++ Example Code:

//C++ program Concatenation C-type string
#include<iostream>
#include<cstring>
using namespace std;

int main(){

  char str1[10] = "Learning";
  char str2[10] = "Coding";

  strcat(str1, str2);
  cout<<str1<<endl;

  return 0;
}

Output:

LearningCoding

Note: C-type string does not support the use of operators on string that's one of the reason we cannot use + operator to concatenate two C-type or Character type string in C++. (alert-success)

Next:

(getButton) #text=(Relational Operator on String Object in C++) #icon=(link) #color=(#2339bd)

C++ Program to Find Volume of Sphere.

A Sphere is a geometrical three-dimensional ball-like structure with no face. It is basically a set of points that are present at an equal distance from a given point in three-dimensional space and this equal distance r is known as the radius of the Sphere. 

In this post, we are going to learn how to calculate the volume of a sphere and how to implement the same in C++ programming.

The volume of any object is basically the amount of space that the object takes in three-dimensional space. The simple formula to calculate the volume of a sphere is shown below.

C++ Example Code:

//C++ Code Implementation for Volume of Sphere
#include<iostream>
using namespace std;

int main(){
    int r;
    float volume;

    cout<<"Calculate the volume of the Sphere."<<endl;
    cout<<"Enter the radius of Sphere: ";
    cin>>r;

    volume = (4/3) * 3.14 * r * r * r;
    cout<<"The Volume of Sphere: "<<volume<<endl;

    return 0;
}

Output:

Calculate the volume of the Sphere.
Enter the radius of Sphere: 4.5
The volume of Sphere: 200.96 

Next:

(getButton) #text=(C++ Program to Find Volume of a Cube) #icon=(link) #color=(#2339bd)

C++ Program to Find Volume of a Cube.

A Cube is a geometrical three-dimensional shape formed by six equal square faces. It contains a total of 8 vertices and 12 similar size edges. If we consider the length of any one edge of the cube as a unit then the area of each face of the cube will be a^2. A Cube is a 3D object with length, breadth, and height the volume of a cube will be equal to length x breadth x height and as in our case, all sides are of equal length so the volume of our cube will be a^3.

Here in this post, we will find the volume of a cube with the help of C++ programming. 

C++ Example Code:

//C++ Code Implementation for Volume of Cube
#include<iostream>
using namespace std;

int main(){
    int a, volume;

    cout<<"Calculate the volume of the Cube."<<endl;
    cout<<"Enter the length of the side of Cube: ";
    cin>>a;

    volume = a * a * a;
    cout<<"The Volume of Cube: "<<volume<<endl;

    return 0;
}

Output:

Calculate the volume of the Cube.
Enter the length of the side of Cube: 6
The volume of Cube: 216

In the above code, we have used integer data type to calculate the volume of the cube but if you are dealing with decimal values then it is recommended to use float data type to calculate as it has the capability to represent decimal values.

Next:

(getButton) #text=(C++ Program to Count Vowels in a String) #icon=(link) #color=(#2339bd)