Let A[1..n] be an array with n numbers. An element x in A[1..n] is said to be co
ID: 3921766 • Letter: L
Question
Let A[1..n] be an array with n numbers. An element x in A[1..n] is said to be cool if it appears more than n 2 times in A[1..n]. For instance, 5 is cool in [5, 1, 5, 2, 5, 2, 5], but in [1, 4, 2, 6, 5, 4, 4, 4], no element is cool. Design a O(n) time algorithm that decides whether or not there is a cool element in A[1..n]. If there is no cool element, the algorithm must return “No”. If there is a cool element, the algorithm must return the value of the cool element. Explain why your algorithm is correct and why it does take O(n) time.
Explanation / Answer
package com.app.test;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class CheggAlgorithm {
int[ ] numbers = new int[n];
public CheggAlgorithm() {
}
public void coolElement(int coolElementArray[])
{
int count=0,coolelement,first,curr_count=0,freq_num=0;
for(int j=0;j<coolElementArray.length;j++){
first = coolElementArray[j];
for(int k=1;k<coolElementArray.length;k++){
if(first==coolElementArray[k] && first!=freq_num){
curr_count++;
}
if(count<curr_count)
{
count=curr_count;
curr_count =1;
freq_num = first;
}
}
}
if(count>coolElementArray.length/2){
System.out.println("The Cool Element is "+freq_num);
}
else
{
System.out.println("There is no any Cool Element");
}
}
public static void main(String[] args) {
CheggAlgorithm algo = new CheggAlgorithm();
Scanner scan = new Scanner(System.in);
System.out.println("Enter the values do yo want to enter the array? ");
int n = scan.nextInt();
System.out.println(n);
for(int loopindex=0;loopindex<n;loopindex++)
{
algo.numbers[loopindex] = scan.nextInt();
}
algo.coolElement(algo.numbers);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.