Solution code in C, C++, Python, Java
Problem statement:-
Given an array of bird sightings where every element represents a bird type id, determine the id of the most frequently sighted type. If more than 1 type has been spotted that maximum amount, return the smallest of their ids.
Example
There are two each of types and , and one sighting of type . Pick the lower of the two types seen twice: type .
Function Description
Complete the migratoryBirds function in the editor below.
migratoryBirds has the following parameter(s):
- int arr[n]: the types of birds sighted
Returns
- int: the lowest type id of the most frequently sighted birds
Input Format
The first line contains an integer, , the size of .
The second line describes as space-separated integers, each a type number of the bird sighted.
Constraints
5<=n<=2X10^5
- It is guaranteed that each type is , , , , or .
Sample Input 0
6 1 4 4 4 5 3Sample Output 0
4Explanation 0
The different types of birds occur in the following frequencies:
- Type : bird
- Type : birds
- Type : bird
- Type : birds
- Type : bird
The type number that occurs at the highest frequency is type , so we print as our answer.
Sample Input 1
11 1 2 3 4 5 4 3 2 1 3 4Sample Output 1
3Explanation 1
The different types of birds occur in the following frequencies:
- Type :
- Type :
- Type :
- Type :
- Type :
Two types have a frequency of , and the lower of those is type .
C Code:-
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
char* ltrim(char*);
char* rtrim(char*);
char** split_string(char*);
int parse_int(char*);
/*
* Complete the 'migratoryBirds' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER_ARRAY arr as parameter.
*/
int migratoryBirds(int arr_count, int* arr) {
int i,max=0,c,j,ans;
for(i=1;i<=100;i++)
{
c=0;
for(j=0;j<arr_count;j++)
{
if(i==arr[j])
c++;
}
if(max<c)
{
max=c;
ans=i;
}
}
return ans;
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
int arr_count = parse_int(ltrim(rtrim(readline())));
char** arr_temp = split_string(rtrim(readline()));
int* arr = malloc(arr_count * sizeof(int));
for (int i = 0; i < arr_count; i++) {
int arr_item = parse_int(*(arr_temp + i));
*(arr + i) = arr_item;
}
int result = migratoryBirds(arr_count, arr);
fprintf(fptr, "%d\n", result);
fclose(fptr);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) {
break;
}
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
break;
}
alloc_length <<= 1;
data = realloc(data, alloc_length);
if (!data) {
data = '\0';
break;
}
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
data = realloc(data, data_length);
if (!data) {
data = '\0';
}
} else {
data = realloc(data, data_length + 1);
if (!data) {
data = '\0';
} else {
data[data_length] = '\0';
}
}
return data;
}
char* ltrim(char* str) {
if (!str) {
return '\0';
}
if (!*str) {
return str;
}
while (*str != '\0' && isspace(*str)) {
str++;
}
return str;
}
char* rtrim(char* str) {
if (!str) {
return '\0';
}
if (!*str) {
return str;
}
char* end = str + strlen(str) - 1;
while (end >= str && isspace(*end)) {
end--;
}
*(end + 1) = '\0';
return str;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
int parse_int(char* str) {
char* endptr;
int value = strtol(str, &endptr, 10);
if (endptr == str || *endptr != '\0') {
exit(EXIT_FAILURE);
}
return value;
}
C++ Code:-
#include <bits/stdc++.h>
using namespace std;
string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);
/*
* Complete the 'migratoryBirds' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER_ARRAY arr as parameter.
*/
int migratoryBirds(vector<int> arr) {
int i,max=0,c,j,ans,n=arr.size();
for(i=1;i<=100;i++)
{
c=0;
for(j=0;j<n;j++)
{
if(i==arr[j])
c++;
}
if(max<c)
{
max=c;
ans=i;
}
}
return ans;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string arr_count_temp;
getline(cin, arr_count_temp);
int arr_count = stoi(ltrim(rtrim(arr_count_temp)));
string arr_temp_temp;
getline(cin, arr_temp_temp);
vector<string> arr_temp = split(rtrim(arr_temp_temp));
vector<int> arr(arr_count);
for (int i = 0; i < arr_count; i++) {
int arr_item = stoi(arr_temp[i]);
arr[i] = arr_item;
}
int result = migratoryBirds(arr);
fout << result << "\n";
fout.close();
return 0;
}
string ltrim(const string &str) {
string s(str);
s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);
return s;
}
string rtrim(const string &str) {
string s(str);
s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
s.end()
);
return s;
}
vector<string> split(const string &str) {
vector<string> tokens;
string::size_type start = 0;
string::size_type end = 0;
while ((end = str.find(" ", start)) != string::npos) {
tokens.push_back(str.substr(start, end - start));
start = end + 1;
}
tokens.push_back(str.substr(start));
return tokens;
}
Python Code:-
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'migratoryBirds' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER_ARRAY arr as parameter.
#
def migratoryBirds(arr):
n=len(arr)
ans,max = 0,0
for i in range(1,101):
c=0
for j in range(n):
if(i==arr[j]):
c+=1
if(max<c):
max=c;
ans=i;
return ans;
# Write your code here
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
arr_count = int(input().strip())
arr = list(map(int, input().rstrip().split()))
result = migratoryBirds(arr)
fptr.write(str(result) + '\n')
fptr.close()
Java Code:-
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
class Result {
/*
* Complete the 'migratoryBirds' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER_ARRAY arr as parameter.
*/
public static int migratoryBirds(List<Integer> arr) {
// Write your code here
int [] birds = new int [5];
for(Integer id : arr) {
birds[id-1] = birds[id-1] + 1;
}
int max = 0;
int id = 0;
for(int i = 0; i < 5; i++) {
if(birds[i] > max) {
max = birds[i];
id = i + 1;
}
}
return id;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int arrCount = Integer.parseInt(bufferedReader.readLine().trim());
String[] arrTemp = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
List<Integer> arr = new ArrayList<>();
for (int i = 0; i < arrCount; i++) {
int arrItem = Integer.parseInt(arrTemp[i]);
arr.add(arrItem);
}
int result = Result.migratoryBirds(arr);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
No comments:
Post a Comment