PROBLEM 1: The function num_distinct to the right takes an array a[] of n integers and determines the number of distinct values in the array. This number is then returned. Examples: [5, 5, 5, 5, 5] has one distinct value. [1, 2, 3, 4, 5] has five distinct values. [1, 2, 3, 2, 1] has three distinct values. Take a few minutes to understand the logic of the function and why it works.	int num_distinct(int a[], int n){ int i, j, ndistinct; bool is_dup; ndistinct=0; for(i=0; i is_dup=false; for(j=0; j if(a[j] == a[i]) is_dup = true; } if(!is_dup) ndistinct++; } return ndistinct; }
Your job: write a linked-list version of exactly the same algorithm. A linked list is a sequence of elements just like an array after all -- i.e., a given linked list either has duplicates or it does not. Use the struct and function prototype below.

struct node {

int val;

node *next;

};

}

You will submit your code just within your homework document (i.e., you are not submitting your .cpp file). Of course, you are free and encouraged to try out your solution in a real program.

PROBLEM 2: Consider a finite set S with n elements; the number of distinct subsets of S with exactly two is called "n choose 2" and typically written as n2. You may Recall that n2=n(n-1)2.

Below is a (trivial) C++ function which takes a non-negative integer n and returns n2 (also a non-negative integer):

unsigned int n_choose_2(unsigned int n) {

if(n==0)

return 0;

else

return n*(n-1)/2;

}

Your job: write a function which also returns n2 but with the following constraints:

• You cannot use the multiplication operator *
• You cannot use the division operator /
• You cannot have any loops
• You cannot add any additional parameters to the function
• Your function must be self-contained: no helper functions!
• You cannot use any globals
• You cannot use any static variables
• You cannot use any "bit twiddling" operations -- no shifts, etc.

However,

• You can use recursion
• You can use the + and - operators.

You will submit a scanned hardcopy (hand-written or printed) or pdf via gradescope. Of course, you are free to try out your solution in a real program.

In addition: argument of correctness required!

You must explain the logic of your solution! In other words, explain why it works. Think in terms of an inductive argument.

Just giving a correct C++ function is not sufficient and will not receive many points (possibly zero!)

Another note: an example is not an argument of correctness!