Arrays: Getting hang of it
Ready for another exciting practice session!? Buckle up, gather your tools (pen & paper if required for dry run) and we'll start with the problems 🚀
Problem 1: Insert element in array
Write a C++ program to insert an element in an array at the specified position.
Input
Input size of array: 5
Array elements: 10, 20, 30, 40, 50
Element to insert: 25
Position where to insert: 3Output
Elements of array are: 10, 20, 25, 30, 40, 50Intuition
Firstly, let's discuss the size of array that we are going to create. Till now, we created an array of the size as specified by the user but now since, we want to insert an element, we'll create an array of size + 1.
Now let's understand what position means in terms of array index. If you observe the sample input, the index for the input position is just position - 1 (this is because the index starts from 0 rather than 1). Example: Element insertion at position 3 means insertion at index 2 and so on.
Once the user has given the position input, first check that it's a valid position as in it's not negative or not greater than the size + 1 of array. If invalid, then simply return invalid position.
Now, if this has to be manually done then all the elements before the position would be the same and all the elements after the position would be moved forward by 1 place to make space at the position.
To achieve this, I'll run a loop on array starting from size and will go till position. Inside the loop we'll keep making arr[i] = arr[i-1]. Finally, after shifting all the required elements, place the input element num at the required position as arr[pos-1] = num.
Logic
- Input size and elements in array. Store it in some variable say
sizeandarr. - Input new element and position to insert in array. Store it in some variable say
numandpos. - To insert new element in array, shift elements from the given insert position to one position right. Hence, run a loop in descending order from
sizetoposto insert. The loop structure should look likefor(i=size; i>=pos; i--).
Inside the loop copy previous element to current element byarr[i] = arr[i - 1];. - Finally, after performing shift operation. Copy the new element at its specified position i.e.
arr[pos - 1] = num;
Solution
#include <iostream>
using namespace std;
int main()
{
int i, size, num, pos;
/* Input size of the array */
cout << "Enter size of the array: " << endl;
cin >> size;
/* Create array */
int arr[size + 1];
/* Input elements in array */
cout << "Enter elements in array: " << endl;
for (i = 0; i < size; i++)
{
cin >> arr[i];
}
/* Input new element and position to insert */
cout << "Enter element to insert: " << endl;
cin >> num;
cout << "Enter the element position: " << endl;
cin >> pos;
/* If position of element is not valid */
if (pos > size + 1 || pos <= 0)
{
cout << "Invalid position! Please enter position between 1 to " << size;
}
else
{
/* Make room for new array element by shifting to right */
for (i = size; i >= pos; i--)
{
arr[i] = arr[i - 1];
}
/* Insert new element at given position and increment size */
arr[pos - 1] = num;
size++;
/* Print array after insert operation */
cout << "Array elements after insertion: ";
for (i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
}
return 0;
}
Problem 2: Delete element from array
Write a C++ program to delete an element from array at specified position.
Input
Input array elements: 10 20 30 40 50
Input position to delete: 2Output
Array elements: 10, 30, 40, 50Intuition
Similar to the last question, nothing needs to be done till the position pos from where the element needs to be removed. Also the equivalent index for given pos would be pos-1. Starting from this point, we would be iterating till the end of array and shift all elements to their previous positions by arr[i] = arr[i+1]. This would have removed the element and even filled the gap as we shifted all proceeding elements to the previous positions but what to do with the last position, it's not required anymore as we have already shifted to its previous position? I'll simply reduce the array size by 1 and voila! we have the updated array.
PS: Don't forget to check that the position provided by user is a valid position from 1 to size of array.
Logic
- Move to the specified location which you want to remove in given array.
- Copy the next element to the current element of array. Which is you need to perform
array[i] = array[i + 1]. - Repeat above steps till last element of array.
- Finally decrement the size of array by one.
Solution
#include <iostream>
using namespace std;
int main()
{
int i, size, pos;
/* Input size and elements in array */
cout << "Enter size of the array: " << endl;
cin >> size;
int arr[size];
cout << "Enter elements in array: " << endl;
for (i = 0; i < size; i++)
{
cin >> arr[i];
}
/* Input element position to delete */
cout << "Enter the element position to delete: " << endl;
cin >> pos;
/* Invalid delete position */
if (pos < 0 || pos > size)
{
cout << "Invalid position! Please enter position between 1 to " << size;
}
else
{
/* Copy next element value to current element */
for (i = pos - 1; i < size - 1; i++)
{
arr[i] = arr[i + 1];
}
/* Decrement array size by 1 */
size--;
/* Print array after deletion */
cout << "Elements of array after delete are: ";
for (i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
}
return 0;
}
Problem 3: Find frequency of each array element
Write a C++ program to input elements in array and find frequency of each element in array.
Input
array elements: 5, 10, 2, 5, 50, 5, 10, 1, 2, 2Output
Frequency of 5 = 3
Frequency of 10 = 2
Frequency of 2 = 3
Frequency of 50 = 1
Frequency of 1 = 1Intuition
I need to calculate frequencies of all elements of array. Now since there are so many elements and I need to calculate frequencies for each of them, I'll create another array freq that will store these frequencies for element at each index.
I'll run a loop as usual for (i = 0 to size) to iterate over array elements but how to keep track fo their frequencies? The frequency count of current element arr[i] is 1 i.e. that element itself. I now need to go to every other element of array and check if it's equal to the current element. If yes, then I'll increment this count. To achieve this I'll run another loop on j from i+1 to size and keep comparing it to arr[i].
After the inner loop finishes counting all the duplicates, you store the total count in the freq array for the current element. freq[i] = count. The outer loop continues to the next element, and the process repeats until all elements have been selected and their frequencies counted.
Now, I might have 3 1s in my array so do I need to calculate frequency 3 times? Needless right? So I'll calculate the frequency of 1 whenever I encounter it first and while comparing it with arr[j], I'll make the frequencies of all proceeding 1s as 0 in the freq array to mark it as already evaluated.
What will our freq array elements be initialized with? It can't be 0 as that's for different purposes, and values > 0 can be actual frequencies. So let's initialize it with -1 as anyway we'll update it eventually.
Logic
- Input size and elements in array from user. Store it in some variable say
sizeandarr. - Declare another array with same size as of input array size to store frequency of each array elements. Say
freqwill store frequencies of all array elements. - To count frequency of each element we require two loops. One outer loop to select an array element. Second inner loop to find first duplicate element of the currently selected array element by outer loop. Run an outer loop from 0 to
size. The loop structure must look likefor(i=0; i<size; i++). - Inside outer loop, initialize
countvariable with 1 to count total frequency of the currently selected array element. - Run an inner loop to count total duplicates of currently selected array element. Run an inner loop from
i + 1tosize. The loop structure should look likefor(j = i + 1; j < N; j++). - Inside inner loop, if duplicate element is found increment the frequency count of current array element. Which is
if(arr[i] == arr[j])thencount++. - After all duplicates has been counted. Store total duplicate count of current element in frequency array. Which is say
freq[i] = count. - Finally print
freqarray to get frequencies of each array element.
Solution
#include <iostream>
using namespace std;
int main()
{
int arr[100], freq[100];
int size, i, j, count;
/* Input size of array */
cout << "Enter size of array: " << endl;
cin >> size;
/* Input elements in array */
cout << "Enter elements in array: " << endl;
for (i = 0; i < size; i++)
{
cin >> arr[i];
/* Initially initialize frequencies to -1 */
freq[i] = -1;
}
for (i = 0; i < size; i++)
{
count = 1;
for (j = i + 1; j < size; j++)
{
/* If duplicate element is found */
if (arr[i] == arr[j])
{
count++;
/* Make sure not to count frequency of the same element again */
freq[j] = 0;
}
}
/* If frequency of the current element is not counted */
if (freq[i] != 0)
{
freq[i] = count;
}
}
/*
* Print frequency of each element
*/
cout << "Frequency of all elements of array: \n";
for (i = 0; i < size; i++)
{
if (freq[i] != 0)
{
cout << arr[i] << " occurs " << freq[i] << " times\n";
}
}
return 0;
}
Problem 4: Merge two arrays into one
Write a C++ program to input elements in two arrays and merge two arrays into a third array.
Input
first array elements: 1, 4, 6, 9, 15
second array elements: 2, 5, 8, 10Output
Merged array in ascending order = 1, 2, 4, 5, 6, 8, 9, 10, 15Intuition
Let my lazy mind get to work again xD Since the arrays are sorted, I'll iterate over both the arrays and simply keep adding the smaller element among the 2 arrays. So let's create 2 variables: index1 and index2, both set to 0. These variables keep track of the merged elements from the given two arrays individually.
Also, we need to create a merge_array that would store the merged elements from both the arrays and we would be returning in the output. Can you guess its size? Since it would contain all elements of both array1 and array2, it's size merge_size would be the summ of size of both the input arrays: size1 + size2.
Now run a loop for merge_array starting from 0 to merge_size something like for(merge_index=0; merge_index<merge_size; merge_index++). Inside the loop, we would perform our major task as said in the first para: compare the elements of both the arrays and add the smaller one.
If the element from the first array is smaller, you assign it to the current position in the merge_array and increment index1. Otherwise, you assign the element from the second array and increment index2.
After the loop, you've merged elements from both arrays up to the point where the smaller elements are exhausted in one of the arrays.
If there are remaining elements in either of the input arrays, you merge them into the merge_array after the loop. You might need two separate loops for this, checking if index1 or index2 is less than their respective sizes. If yes, then add the remaining elements in merge_array.
Understand with an example:
Array 1: 1, 2, 4
Array 2: 3, 5, 6, 14
Now index1 is at 0th index of array1 and index2 is at 0th index of array2.
- Compare both elements on these indices:
1 < 3so add 1 to merge_arrary and move index1 to 1st index. - Compare again:
2 < 5so again add 2 to merge_array and move index1 to 2nd index.merge_indexis also constantly moving as we are doing this inside the loop overmerge_array.merge_indexwould be currently at 1st index. merge_indexwould now be at 2nd index. Now compare4 > 3. So add 3 to merge_array and move index2 to 1st index.4 < 5: add 4 to merge_array and index1 reaches thesize1ofarray1. But have we added all elements of both arrays to merge_array? No right. Elements of array2 are still left, so let's add them too.- Run a loop as
while (index2 < size2). Keep adding array2 elements to merge_array and keep incrementing index2 & merge_index.
Logic
- Input size and elements in two arrays and store them separately in two array variables: say
size1,arr1,size2, andarr2store the size and elements of the first and second arrays, respectively. - Create another array that will store the merged array with size
merge_size = size1 + size2, saymerge_array[merge_size]. - Initialize two variables
index1 = 0andindex2 = 0. Both these variables will keep track of the total merged elements from the given two arrays individually. - Run a loop from 0 to merge_size. The loop structure must look like
for(merge_index = 0; merge_index < merge_size; merge_index++). - Inside the loop, check for the smallest element in the two input arrays, which is
if(arr1[index1] < arr2[index2]), then assign the element of the first array to the merge array, i.e.,merge_array[merge_index] = arr1[index1]and increment index1. Otherwise, storemerge_array[merge_index] = arr2[index2]and increment index2. - After loop merge the remaining array elements if any.
Solution
#include <iostream>
using namespace std;
int main()
{
int size1, size2, merge_size;
int index1, index2, merge_index;
int i;
/* Input size of first array */
cout << "Enter the size of the first array: " << endl;
cin >> size1;
int arr1[size1];
/* Input elements in the first array */
cout << "Enter elements in the first array: " << endl;
for (i = 0; i < size1; i++)
{
cin >> arr1[i];
}
/* Input size of the second array */
cout << "\nEnter the size of the second array: " << endl;
cin >> size2;
int arr2[size2], merge_array[size1 + size2];
/* Input elements in the second array */
cout << "Enter elements in the second array: " << endl;
for (i = 0; i < size2; i++)
{
cin >> arr2[i];
}
merge_size = size1 + size2;
/*
* Merge two arrays in ascending order
*/
index1 = 0;
index2 = 0;
for (merge_index = 0; merge_index < merge_size; merge_index++)
{
/*
* If all elements of one array
* are merged to the final array
*/
if (index1 >= size1 || index2 >= size2)
{
break;
}
if (arr1[index1] < arr2[index2])
{
merge_array[merge_index] = arr1[index1];
index1++;
}
else
{
merge_array[merge_index] = arr2[index2];
index2++;
}
}
/*
* Merge remaining array elements
*/
while (index1 < size1)
{
merge_array[merge_index] = arr1[index1];
merge_index++;
index1++;
}
while (index2 < size2)
{
merge_array[merge_index] = arr2[index2];
merge_index++;
index2++;
}
/*
* Print merged array
*/
cout << "\nArray merged in ascending order: ";
for (i = 0; i < merge_size; i++)
{
cout << merge_array[i] << " ";
}
return 0;
}Problem 5: Search in an array
Write a C++ program to input elements in array and search whether an element exists in array or not.
Input
size of array: 10
elements in array: 10, 12, 20, 25, 13, 10, 9, 40, 60, 5Output
Element to search is: 25
Element found at index 3
Intuition
Suppose you are standing in front of a students queue and you have to search for Ritu in that entire queue. What I'll do is I'll start looking every student one by one and check if he/ she's Ritu or not. Once I see Ritu, I'll say that I found her! Similarly, we are going to search for the element here as well.
Let the element to search be num. I'll also create a variable found that can have two values 0 & 1 where value 0 indicates Not found and 1 indicates Found. Now obviously, the initial value of found would be 0.
I'll iterate over the array from 0 to size and keep checking if arr[i] = num. If yes, then make found as 1 and break from the loop.
Now after the loop simply check the value of found. If it's 1 then print Found at position i + 1. If the value is 0 then print Not found.
Note that we printed i+1 as we want the position of element and not the index.
Logic
- Input size and elements in array from user. Store it in some variable say
sizeandarr. - Input number to search from user in some variable say
num. - Define a flag variable as
found = 0. I have initializedfoundwith 0, which means initially I assumed that searched element does not exists in array. - Run loop from 0 to
size. Loop structure should look likefor(i=0; i<size; i++). - Inside loop check if current array element is equal to searched number or not. Which is
if(arr[i] == num)then setfound = 1flag and terminate from loop. Since element is found no need to continue further. - Outside loop
if(found == 1)then element is found otherwise not.
Solution
#include <iostream>
using namespace std;
int main()
{
int size, i, num, found;
/* Input size of array */
cout << "Enter size of array: " << endl;
cin >> size;
int arr[size];
/* Input elements of array */
cout << "Enter elements in array: " << endl;
for (i = 0; i < size; i++)
{
cin >> arr[i];
}
cout << "Enter element to search: " << endl;
cin >> num;
/* Assume that the element does not exist in the array */
found = 0;
for (i = 0; i < size; i++)
{
/*
* If the element is found in the array then raise the found flag
* and terminate from the loop.
*/
if (arr[i] == num)
{
found = 1;
break;
}
}
/*
* If the element is found in the array
*/
if (found == 1)
{
cout << "\n" << num << " is found at position " << i + 1;
}
else
{
cout << "\n" << num << " is not found in the array";
}
return 0;
}
I hope now you are getting a grip on the array concepts. Not yet? Let's master it in the next article!