Problem 2: NOTE: NO CODING JUST EXPLANATIONS 1) Determine if 2 arrays contain th

Question

Problem 2:

NOTE: NO CODING JUST EXPLANATIONS

1) Determine if 2 arrays contain the same elements

2) Counting total number characters that have a duplicate within a string (i.e. "gigi the gato" would result in 7 (g x 3 + i x 2 + t x 2)

3) Finding an empty row in a 2-D array where empty is defined as an element with a 0 entry.

For each problems segment given above, do the following:

- Create an algorithm(PSEUDOCODE) to solve the problem - Identify the factors that would influence the running time, and which can be known before the algorithm or code is executed. Assign names (such as n) to each factor.

- Identify the operations that must be counted. You need not count every statement separately. If a group of statements always executes together, treat the group as a single unit. If a method is called, and you do not know the running time of that method, count it as a single operation.

- Count the operations performed by the algorithm or code. Express the count as a function of the factors you identified in Step 2. If the count cannot be expressed as a simple function of those factors, define the bounds that can be placed on the count: the best case (lower bound) and worst case (upper bound).

- Determine what the Best Case Inputs are, and the Worst Case Inputs are, and the efficiency of your implementation - Transform your count formula into big-O notation by:

- Taking the efficiency with worst case input

- Dropping insignificant terms.

- Dropping constant coefficients.

Explanation / Answer

Problem 2:

Here we can use caount array

1. create a count array of size 26
   int count[26] = {0}; // initialize with zero
2.
   //traverse through each character of string and incremented count of given character
   for(int i=0; i<size; i++){
       char c = toUpper(str[i]); // convert given charater into lower(treating lower and upper as same)
       count[c - 65]++; // ASCII character of A = 65
   }
  
3. traverse through count array, if count > 1, then add this count value into result
   int result = 0;
   for(int i=0; i<26; i++)
       if(count[i] > 1)
           result = result + count[i]

4.
   return result

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.