In this lesson, we have a few challenges for you.

Exercise 1: Remove all occurrences

Given an integer array nums and an integer val, remove all occurrences of val in nums in place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the nums array. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Sample input

Value to be removed      : 2
Before Removal nums[]    : {0 1 2 2 3 0 4 2 }
After Removal nums[]     : {0 1 3 0 4 }

Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4. Note that the five elements can be returned in any order. It does not matter what you leave beyond the returned k.

#include <iostream>
#include <iomanip> // a C++ library that includes a collection of tools for 
           // input output manipulation, includes setw() 
using namespace std;

void print(const char msg[], int nums[], int size)
{
    cout << setw(22) << msg << " : {";
    for(int i=0; i<size; i++)
        cout << nums[i] << " ";
    cout << "}";
}

int removeAllOccurences(int nums[], int numsSize, int val)
{
    // Write your code here
}
int main()
{
    int nums[] = {0,1,2,2,3,0,4,2}, val = 2, size = 8;

    print("Before Removal nums[]", nums, size);
    // Call your function here


    // --------------------------------------
    print("After Removal nums[]", nums, size);
    return 0;
}
Remove all occurrences

The iomanip library in C++ includes a collection of tools for manipulating the format of input and output streams. We’re using this because we use the manipulator setw to set the width of the field in which the next data value is to be written.

Hint: You may work with these four ideas.

Exercise 2: Find equilibrium

Write a program that keeps on taking input from the user until the user enters -99 (at maximum 100 values). After taking input, your program should return an equilibrium index of an array. If no equilibrium index is found, then your program should return -1.

An index of an array is said to be an equilibrium index if the sum of the elements on its lower indexes is equal to the sum of elements at higher indexes.

Look at the animation below for better understanding:

Write your code in the playground below:

#include <iomanip>
#include <iostream>
using namespace std;

int equilibriumIndex(int nums[], int numsSize)
{
    //write your code here
    
}
void print(const char msg[], int nums[], int size)
{
    cout << setw(22) << msg << " : {";
    for(int i=0; i<size; i++)
        cout << nums[i] << " ";
    cout << "}";
}
int main()
{
    int nums[] = {7,-1,-5,2,4,-3,0}, size = 7;

    print("Before Removal nums[]", nums, size);
    
    size = equilibriumIndex(nums, size);

    print("After Removal nums[]", nums, size);
}
Equilibrium index

Exercise 3: Sorted or not

Take a single-dimensional array from a file and determine whether the array read is a sorted array or not.

Sorted in ascending order

At each index, the condition A[i]<=A[i+1] must be true. Therfore, for checking an array to be in ascending order, we check the opposite of this condition. If it is so, we can declare it to not be an ascending array.

Look at the animation below for a better understanding.

Sorted in descending order

On the other hand, the condition A[i]>=A[i+1] must be true for an array to be in descending order.

Look at the animation below for a better understanding:

Instruction: Write the code of the three functions. The isSorted() method checks for both ascending and descending orders if any of the cases is true it returns true otherwise, it returns false. 

#include <iostream>
#include <iomanip>
using namespace std;
bool IsDescendingArray(int A[], int size)
{
    // write your code here. 
}
bool IsAscendingArray(int A[], int size)
{
    // write your code here.
}
bool IsSorted(int A[], int size)
{
    // write your code here.
}
void print(const char msg[], int nums[], int size)
{
    cout << setw(22) << msg << " : {";
    for(int i=0; i<size; i++)
        cout << nums[i] << " ";
    cout << "} \n\n";
}
int main()
{
    int nums[] = {7,-1,-5,2,4,-3,0}, size =7;
    bool sorted = false;

    print("The array ", nums, size);
    IsDescendingArray(nums, size);
    IsAscendingArray(nums, size);
    sorted = IsSorted(nums, size);
    if(sorted == true)
        cout << "The array is sorted." << endl;
    else
        cout << "The array is not sorted." << endl;

    return 0;
}
Sorted or not

Exercise 4: The Sieve of Eratosthenes

The Greek mathematician, Eratosthenes, came up with the following algorithm to quickly find all prime numbers between 2 and a given number nn. How does it work?

  1. Start with d = 2.
  2. Cross out all multiples of d greater than d and less than or equal to n.
  3. Set d equal to the next uncrossed number.
  4. If d is greater than square_root of n, stop.
  5. Else, repeat from step 2.
  6. Report all uncrossed elements between 2 and n as primes.

Write a function called sieveOfEratosthenes(). This function will accept a number n and returns all the primes between 2 and n as an array (passed as a parameter). It should also return the count of these prime numbers.

#include <iostream>
using namespace std;
int sieveOfEratosthenes(int A[], int n)
{
    // Write your code here
}

void allPrimesBetween1_N(int N)   // N <=100000
{
    const int Capacity =100000;   
    int A[Capacity]={};
    int primesCount = sieveOfEratosthenes(A, N);
    cout << "Found "<<primesCount << " primes between 1 to "<<N<<endl;
    cout << "The Primes are: {";
    for(int i=0; i<=N; i++)
    {
        if(A[i]!=-1)
        {
            cout << i << " ";
        }
    }
}
int main()
{    
    allPrimesBetween1_N(1000);
    return 0;
}
Sieve of Eratosthenes

Exercise 5: Trapping rainwater

We have an elevation map with non-negative integers in which each bar width is equal to 1. We want to calculate the trapped water after rain.

Press + to interact
Trapped rainwater
Trapped rainwater

Sample input

[0,1,0,2,1,0,1,3,2,1,0,3,2,1,2]

where each number represents the height.

Sample output

12 units

The dark blue section in the evaluation map above represents the wall, and the light blue section represents trapped water. So the 12 units of water (light blue) are trapped.

Look at the animation below to understand the algorithm.

The algorithm should work in two passes. First, it finds the maximum height index, and then it starts from the left-most height to that maximum height and then in the second pass it starts from the right-most height to the maximum height.

#include <iostream>
using namespace std;
int trap(int height[], int heightSize)
{
    //Write your code here
}
int main()
{    
    //call your function here
    return 0;
}
Trapping rainwater

Exercise 6: Container with the most water

You are given an integer array height of length n. There are n vertical rods such that the two endpoints of the ith line are (i, 0) and (i,height[i]).

Find two lines that, together with the x-axis, form a container such that the container contains the most water.

Return the maximum amount of water a container can store.

Please note that you may not slant the container.

Sample input

[1,8,6,2,5,4,8,3,7]

Where these numbers represent the respective heights of the rods.

Sample output

49

The above vertical lines are represented by an array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

#include <iostream>
using namespace std;

int trap(int height[], int heightSize)
{
    // write your code here.
}
int main()
{    
    int height[] = {0,1,0,2,1,0,1,3,2,1,2,1}, size = 12;
    int units = trap(height, size);
    cout << "There are " << units << " units of trapped rainwater.";

    return 0;
}
Container with most water

Exercise 7: Merge two sorted arrays

Write a program to merge two sorted arrays.

Sample input

A = { 1 4 6 7 7 8 9 10 }
B = { -1 2 3 7 7 8 9 10 100 200 399 }

Sample output

Merged Array 
C = { -1 1 2 3 4 6 7 7 7 7 8 8 9 9 10 10 100 200 399 }

Look at the animation below:

#include <iostream>
using namespace std;
void mergeSorted_Arrays(int C[], int &CSize, int A[], int ASize, int B[], int BSize)
{
    //Write your code here
}
void print(const char Name[], int A[], int Size)
{
    cout << Name << " = { ";
    for(int i=0; i<Size; i++)
        cout << A[i] << " ";
    cout << "}"<<endl;
}
int main()
{    
    const int Capacity = 100;
    int A[ ] = {1,4,6,7,7,8,9,10}, ASize = sizeof(A)/4;
    int B[ ] = {-1,2,3,7,7,8,9,10,100,200,399}, BSize = sizeof(B)/4;
    int C[Capacity], CSize;
    mergeSorted_Arrays(C, CSize, A, ASize, B, BSize);
    print("A", A,ASize);
    print("B", B,BSize);
    print("Merged Array \nC", C,CSize);
    return 0;
}
Merge two sorted arrays