Waste less time on Facebook — follow Brilliant.
×

Loops

When you need to do a repetitive task, like working through all elements in a list to find a prime or searching a map until you've found all of the gold, loops are a go-to tool.

While

If we have two strictly increasing integer sequences:

\[\begin{align} &a_0,a_1, .... a_{n-1}\\ &b_0,b_1,...,b_m-1 \end{align}\]

The following program finds the number of integers common to both sets. That is the cardinality of the set.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int i = 0;
int j = 0;
int count;

do{
    if (a[i]==b[j]) {
        i++;
        j++;
        count++;
    } else if(a[i] < b[j]) {
        i++;
    } else if(a[i] > b[j]) {
        j++;
    }
} while ((i < x) && (j < y));
print count

If it is given the following two sets as input:

\[\begin{align} a&=\{a_0,a_1,\ldots,a_{78}\}\\ b&=\{b_0,b_1,\ldots,b_{44} \} \end{align}\]

your task is to find the value of the variables in the while loop's conditional statement. Specifically find the value of x and y so that the program runs smoothly given the arrays \(a\) and \(b\).

Input \(x + y\) as your answer.

View solution
View wiki
by Brilliant Staff

A binary search tree or BST is a binary tree where each node has a key such that the key in any node is larger than the key of its left child, and less than any node to the right.

example

example

Consider the function exists(tree, value), it verifies if a node with a certain value exists. It can be implemented both iteratively and recursively in pseudo-code as follows:

Iterative version

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
boolean exists(Node root, int goal):
    Node current = root;
    while (current != null):
        if (current.value == goal):
            return true;
        if (goal > current.value):
            current = current.left;
        else:
            current = current.right;
    return false;

Recursive version

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
boolean exists(Node n , int value):
    if (n.value == goal)
        return true;
    if (goal > n.value):
        if exists(n.left)
            return true;
        return false
    else
        if exists(n.right)
            return true;
        return false;

Consider the worst case performance of both methods. Suppose they are only run on a perfectly balanced tree(every non leaf node has two children. Every leaf has no children) with \(N\) nodes.

If the recursive version runs in \(O(f(N))\) and the iterative function runs in \(O(g(N))\), what is \(f(n)/g(n)\)?

View solution
View wiki
by Brilliant Staff

A certain sorting function is described in pseudo code below. Given a multi-set \(a_0\) it returns the multi-set sorted in increasing order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 sort(int[] a){
     int n = a.length;
     for (int i = 1; i < n ; ++i){
         int j = i;
         while (j > 0 and a[j] < a[j - 1]){
             swap(a, j, j - 1);
             j = j - 1;
         }       
     }
 }

swap(array,x,y) swaps the element at index \(x\) element in array with the item at index \(y\).

Suppose the function is given an array \(A\) of length \(n\) that is a worst-case input, i.e. swap is called the maximum possible number of times, how many times is swap called?

View solution
View wiki
by Brilliant Staff
×

Problem Loading...

Note Loading...

Set Loading...