// Arup Guha
// 2/18/2022
// Code for Questions #1,4 All Versions COP 3502 Quiz 2

#include <stdio.h>

int sumTowerDisks(int n);
int prodOfDigits(int n);
int numTerms(int n);
int mysteryA(int* array, int n, int k);
int mysteryB(int* array, int n, int target);
int mysteryC(int* array, int n, int target);

int main(void) {

    // Test each recursive function.
    printf("tower(5) = %d\n", sumTowerDisks(5));
    printf("pD(26419) = %d\n", prodOfDigits(26419));
    printf("nT(12) = %d\n", numTerms(12));

    // Now test each mystery function.
    int verA[10]  = {3, 9, 2, 6, 1, 4, 4, 8, 7, 8};
    printf(" mysA(verA, 10, 5) = %d\n", mysteryA(verA, 10,5));

    int verBC[10]  = {2, 3, 8, 9, 13, 19, 22, 29, 38, 40};
    printf("mB(verBC, 10, 11) = %d\n", mysteryB(verBC, 10, 11));

    printf("mC(verBC, 10, 11) = %d\n", mysteryC(verBC, 10, 11));
    return 0;
}

// Returns the desired sum of disk numbers from the towers of Hanoi.
int sumTowerDisks(int n) {

    // No work.
    if (n == 0) return 0;

    // Middle disk counts as n, then we repeat everything for n-1 disks 2 times.
    return n + 2*sumTowerDisks(n-1);
}

// Returns the product of digits of n.
int prodOfDigits(int n) {

    // Last digit is its own product.
    if (n<10) return n;

    // Otherwise, extract the last digit and multiply by the product of the
    // rest. n%10 is last digit, n/10 is rest.
    return (n%10)*prodOfDigits(n/10);
}

// Returns the number of terms in the sequence starting with n.
int numTerms(int n) {

    // 1 is the last term.
    if (n == 1) return 1;

    // If it's even, we go to n/2 after generating 1 term.
    if (n%2 == 0) return 1 + numTerms(n/2);

    // Otherwise, we go to 5n+1.
    else return 1 + numTerms(5*n+1);
}



// Pre-condition: array is size n and 1 <= k <= n.
int mysteryA(int* array, int n, int k) {

    // This adds the first k items of the array.
    int res = 0, tmp;
    for (int i=0; i<k; i++)
        res += array[i];
    tmp = res;

    // This slides are window.
    for (int i=0; i<n-k; i++) {

        // Each time, we subtract the left most item and add in the new item to the right.
        tmp = tmp - array[i] + array[i+k];

        // If this window of size k has a higher sum update.
        if (tmp > res) res = tmp;
    }

    // When we get here, we have returned the maximum sum of any k consecutive array values.
    return res;
}

// Pre-condition: array is size n and sorted with unique values.
//                target > 0.
int mysteryB(int* array, int n, int target) {

    int res = 0, low = 0, high = 0;

    // Sweep left to right.
    while (high < n) {

        // Difference between array values is too small, update high.
        if      (array[high] - array[low] < target) high++;

        // Too big, update low.
        else if (array[high] - array[low] > target) low++;

        // Goldilocks - it's just right, count it.
        else {
            res++;
            low++;
            high++;
        }
    }

    // Returns the number of pairs (i, j) where array[j]-array[i] = target.
    return res;
}

int mysteryC(int* array, int n, int target) {

    int res = 0, low = 0, high = 0;

    // Another sweep.
    while (low < n) {

        // array[high]-array[low] is too big or end of range, so add every
        // ordered pair of the form (low, x) such that array[x]-array[low] <= target.
        if (high == n || array[high] - array[low] > target) {
            res += (high-low);
            low++;
        }

        // We can keep on moving high.
        else
            high++;
    }

    // This represents the # of ordered pairs (i, j) where array[j]-array[i] <= target.
    return res;
}