Untitled

///SEMINAR 1: 24/2/2024
#include <iostream>
#include <vector>
// Some questions:
///Seminar 1 - Time Complexity
/// What is an algorithm ?
///==>Algorithm: Input ===> |Algorithm| ===> Output
/// Time complexity ? Why ?
///==> Because  computers have different configuration, it's not useful to judge a program by running time.
/// For example :
int SumUp(int size) {
    int sum = 0; // 1
    for (int i = 0; i < size; i++) { //2n
        sum = sum + i; //3n
    }
    return sum; // 1
}
/// ===> T(n) = 2 + 5n  ==> O(n) = ??
/// The dominant term is the term the one that gets biggest (i.e. dominates) as N gets bigger.
/// Example: n^3 grow faster than n^2
/// Big O notation: f(n) = O(g(n)) ==> limit of f(n)/g(n) with n tend to infinity < infinity or exist n_0, c > 0
/// such that for all n > n_0 f(n) <= c*g(n)
/// Ex: f(n) = n^5 + n^4 + n^3 ===> f(n) ~ O(n^5)
/// Ex: f(n) = n*log(n) + n ===> f(n) ~ O(n*log(n))
/// Ex: f(n) = 2*n + n^(0,5) + n ^ (1,5) ===> f(n) ~ O(n^(1,5))
/// Let's calculate time complexity of following code:
//code 1:
bool isEven(int value) {
    return (value % 2 == 0);
}
/// O(1) Because you're only ever taking one value, there is no "loop" to go through.
///Even as the value gets bigger, you simply divide it by 2 and see whether it returns an integer or a float.

//code 2:
bool areYouHere(const std::vector<int>& arr1, const std::vector<int>& arr2) {
    for (size_t i = 0; i < arr1.size(); i++) {
        for (size_t j = 0; j < arr2.size(); j++) {
            if (arr1[i] == arr2[j]) return true;
        }
    }
    return false;
}
/// O(n^2) because u will go through each array once.
///

//Code 3:
void doubleArrayValues(std::vector<int>& array) {
    for (size_t i = 0; i < array.size(); i++) {
        array[i] *= 2;
    }
}
/// O(n) Reasoning: As `array.length` increases, the number of iterations increases at the same rate.
///This is because you don't have to loop any more than once: however many items are in the array
///is how many times you run the function.

//Code 4:
int naiveSearch(const std::vector<int>& array, int item) {
    for (size_t i = 0; i < array.size(); i++) {
        if (array[i] == item) {
            return i;
        }
    }
    return -1;
}

///O(n) Answer: O(n). Linear run time complexity.
///Reasoning: Same as above with the doubler. You have to check each and every item once and only once
///in order to determine whether you've got a match.

//Code 5:
int calculateY(int n) {
    int y = 0;
    for (int j = 1; j * j <= n; j++) {
        y++;
    }
    return y;
}
///O(√n) because
/// j is still growing linearly, but the loop runs as long as j2 ≤ n. This means that as soon as j exceeds √ n, it will stop
///Therefore, there will only be O(√n) iterations of the loop, and since each one does O(1) work, the total work done is O(√n).

//Code 6:
int efficientSearch(const std::vector<int>& array, int item) {
    int minIndex = 0;
    int maxIndex = static_cast<int>(array.size()) - 1;
    int currentIndex;
    int currentElement;

    while (minIndex <= maxIndex) {
        currentIndex = (minIndex + maxIndex) / 2;
        currentElement = array[currentIndex];

        if (currentElement < item) {
            minIndex = currentIndex + 1;
        } else if (currentElement > item) {
            maxIndex = currentIndex - 1;
        } else {
            return currentIndex;
        }
    }
    return -1;
}
///O(logn)

//Code 7:
void nestedLoopsFunction(int n) {
    int b = 0; // constant
    for (int i = n; i > 0; i--) { // n iterations
        for (int j = 0; j < i; j++) { // runs i times in each iteration
            b = b + 5;
        }
    }
    std::cout << b << std::endl;
}
/// The outer loop runs from n to 1, decrementing i by 1 in each iteration.
/// The inner loop runs i times in each iteration of the outer loop.
/// The total number of iterations for the inner loop can be expressed as the sum of the first n positive integers:  n+(n−1)+(n−2)+…+1
/// This sum is known as the arithmetic series sum and is equal to n*(n+1)/2
///  the inner loop has a time complexity of O(n^2)

//Code 8:
///You are given two arrays a and b sorted in non-decreasing order and a number S.
///Find such i and j such that the sum a[i] + b[j] = S. Time O(n).

std::pair<int, int> findPairsWithSum(const std::vector<int>& a, const std::vector<int>& b, int S) {
    int i = 0; // Pointer for array a (starting from the beginning)
    int j = b.size() - 1; // Pointer for array b (starting from the end)

    while (i < a.size() && j >= 0) {
        int currentSum = a[i] + b[j];

        if (currentSum == S) {
            // Found a pair with the given sum
            return std::make_pair(a[i], b[j]);
        } else if (currentSum < S) {
            // Move the pointer in array a to the right to increase the sum
            i++;
        } else {
            // Move the pointer in array b to the left to decrease the sum
            j--;
        }
    }

    // No pair found with the given sum
    return std::make_pair(-1, -1);
}


//Code 9:
/// You are given two arrays a and b sorted in non-decreasing order. Find the number of pairs (i, j)
///such that a[i] = b[j] . Time O(n).

int countEqualPairs(const std::vector<int>& a, const std::vector<int>& b) {
    int count = 0;
    int i = 0; // Pointer for array a
    int j = 0; // Pointer for array b

    while (i < a.size() && j < b.size()) {
        if (a[i] == b[j]) {
            // Found a pair (i, j) with ai = bj
            count++;

            // Move both pointers to the next elements
            i++;
            j++;
        } else if (a[i] < b[j]) {
            // Move the pointer in array a to the right
            i++;
        } else {
            // Move the pointer in array b to the right
            j++;
        }
    }

    return count;
}