A Suppose that you are given an array of integers. Write a Java program which pr
ID: 3814925 • Letter: A
Question
A Suppose that you are given an array of integers. Write a Java program which prints out the element or elements that occur least often in the array, and the number of times they occur. For example, for array [1 4 4 3 4 3 5 2 1] your algorithm should print the message: Elements: 5 2 Number of occurrences: 1 The implementation should be done in the main method of your class. The only data structure you are allowed to use is arrays. No hash map etc. You must submit a java file (.java extension). [25%] B What is the time complexity (O()) of your algorithm? Justify your answer. [5%]Explanation / Answer
HI, Please find my implementation.
public class LeastOccurence {
public static void main(String[] args) {
int [] arr = {1,4,4,3,4,3,5,2,1};
// finding least count for any number
int leastCount = Integer.MAX_VALUE; // initializing with max value
for(int i=0; i<arr.length; i++){
int currentCount = 0;
for(int j=0; j<arr.length; j++){
if(arr[i] == arr[j])
currentCount++;
}
if(currentCount < leastCount)
leastCount = currentCount;
}
// storing all those elements in an array
int k=0;
int leastOccrEle[] = new int[arr.length];
for(int i=0; i<arr.length; i++){
int currentCount = 0;
for(int j=0; j<arr.length; j++){
if(arr[i] == arr[j])
currentCount++;
}
// if number of occurence of current element is equal to leastCount
if(currentCount == leastCount){
boolean status = false;
for(int x=0; x<k; x++)
if(leastOccrEle[x] == arr[i]){ // if current element has already considered then don't include
status = true;
break;
}
if(!status)
leastOccrEle[k++] = arr[i];
}
}
// now printing all those elements that have occurence equal to leastCount
System.out.print("Elements: ");
for(int i=0; i<k; i++)
System.out.print(leastOccrEle[i]+" ");
System.out.println(" Number of occurrences: "+leastCount);
}
}
/*
Sample run:
Elements: 5 2
Number of occurrences: 1
*/
Time complexity: O(n^2) we have teo nested for loop running n times each time
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.