For each problems segment given below, do the following: Create an algorithm to
ID: 3696790 • Letter: F
Question
For each problems segment given below, do the following: Create an algorithm 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-0 notation by: Taking the efficiency with worst case input o Dropping insignificant terms, o Dropping constant coefficients. Determine if 2 arrays contain the same elements 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) Finding an empty row in a 2-D array where empty is defined as an element with a 0 entry.Explanation / Answer
Q1. Determine if 2 arrays contains the same elements
We can use HashMap to solve this problem.
1. Add all elements into HashMap with element as key and count as values(number of times elements appears in array)
HashMap<Integer, Integer> hashMap;
2. Now, traverswe through 2nd array.
for each element check whether it is available in hashMap or not. If it is there then decrease
count of that element. IF count value is one then remove from hashMap.
If current element from 2nd array is not present in hashMap, then return false.
boolean isSameElements(int arr1[], int arr2[]){
// create hashMap
HashMap<Integer, Integer> map = new HashMap<>();
for(int x : arr1){
if(map.containKey(x){ // if already there in map, increment count
map.put(x, map.get(x)+1);
}else{
map.put(x, 1);
}
}
// for each element of array 2
for(int y: arr2){
if(!map.containKey(y)) // if not available in map
return false;
if(map.get(y) == 1) // if count is 1 then remove from map
map.remove(y);
else
map.put(y, map.get(y) - 1); // decrement count
}
}
Worst case time complexity: O(n), Space complexity: O(n)
Q2. counting total number of duplicates chracters
1. create a HashMap with key as character and count as value(number of times it appears in string)
2. traverse through map and if count is greater than one then add in result
int countDuplicates(String str){
// building a count map
HashMap<Character, Integer> map = new HashMap<>();
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
if(map.containKey(c)){ // increment count
map.put(c, map.get(c) + 1);
}
else{
map.put(c, 1);
}
}
// traverse through map
int result = 0; // initializing result
for(Map.Entry<Character, Integer> entry: map.entrySet()){
if(entry.getValue() > 1) // if count is greater than one
result = result + entry.getValue();
}
return result;
}
Worst case time complexity: O(n), Space complexity: O(n)
Q3).
Finding empty row in 2d array
1. traverse through each row and check whether current row is empty or not
2. if current row is empty then return true else go for next row
3. if all rows are non-empty then return flase
boolean isEmptyRow(int arr[][], int rows, int cols){
for(int i=0; i<rows; i++){
int j=0;
for(j=0; j<cols; j++){
if(arr[i][j] != 0) // if any entry of current row is not 0 then go for next row
break;
}
if(j == cols) // all entry of current row is 0
return true;
}
return false;
}
Worst case time complexity: O(n^2), Space complexity: O(1)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.