cps 100 random quiz 4

Name: ________________________________

Honor Code Acknowledgment: ___________________

Random Quiz # 4

CPS 100, Fall 1995

Due: September 28

Problem 1: To the People (2 points)

What is the complexity (using big-O notation) of computing the sum of the digits of an integer n using the code segment shown below (why?)

    int sum = 0;
    while (n > 0)
    {
        sum += n % 10;
        n /= 10;
    }

Problem 2 Hautbois (2 points)

Consider a list of integers in which the integers are stored in non-decreasing order and in which the integer k occurs exactly k times; these lists are called N-lists where N is the largest integer in the list. For example, a 4-list is (1,2,2,3,3,3,4,4,4,4) and a five list is a 4-list with (5,5,5,5,5) appended to the end. If for every integer k in an N-list such that N/3 <= k <= 2N/3 , all of the occurrences of k are removed then how many numbers are left (using big-Oh notation)? For example, if N = 9, then after removal the 9-list will be

           (1,2,2,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9)