One day Jay, on getting his first salary, decides to distribute apples among the poverty-stricken persons. He gave each person 1kg of apples. People are coming in a queue and he makes sure that he gives every person 1 kg of apples only once. Every person is identified by a specific integer.
Given the length of the queue N followed by an array of N integers, denoting the persons in that queue, find the minimum kilograms of apples Jay will have to distribute.
Examples:
Input: arr[] = {1, 1, 1, 1, 1}
Output: 1
Explanation: For test case 1, the same person (identified by the integer ‘1’ comes again and again in the queue, but Jay will not give him apples again and again. He gave him apples only once so minimum kg’s of apples here required-1kg).Input: arr[] = {1, 2, 3, 1, 2}
Output: 3
Method 1: To solve the problem follow the below idea:
Iterate over the array and check if there is any duplicate value present. If no duplicates are found then simply increment count. Return count.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int minimum_apple(int arr[], int n){ sort(arr, arr + n); int c = 1; for (int i = 1; i < n; i++) { if (arr[i - 1] != arr[i]) { c++; } } return c;}// Drivers codeint main(){ int arr[] = { 1, 1, 1, 1, 1 }; int n = 5; // Function Call cout << minimum_apple(arr, n) << endl; return 0;} |
C
#include <stdio.h>#include <stdlib.h>int compare(const void *a, const void *b) { return (*(int*)a - *(int*)b);}int minimum_apple(int arr[], int n) { qsort(arr, n, sizeof(int), compare); int c = 1; for (int i = 1; i < n; i++) { if (arr[i - 1] != arr[i]) { c++; } } return c;}int main() { int arr[] = {1, 1, 1, 1, 1}; int n = 5; printf("%d\n", minimum_apple(arr, n)); return 0;} |
Java
import java.io.*;import java.util.*;class GFG { public static void main (String[] args) { int arr[] = {1, 1, 1, 1, 1}; int n=5; System.out.println(minimum_apple(arr,n)); } public static int minimum_apple (int arr[], int n) { Arrays.sort(arr); int c=1; for(int i=1;i<n;i++) { if(arr[i-1]!=arr[i]) { c++; } } return c; }} |
Python3
import numpy as npdef minimum_apple(arr, n): arr.sort() c = 1 for i in range(1, n): if arr[i-1] != arr[i]: c += 1 return carr = np.array([1, 1, 1, 1, 1])n = 5print(minimum_apple(arr, n)) |
C#
// C# implementationusing System;class GFG { static void Main(string[] args) { int[] arr = { 1, 1, 1, 1, 1 }; int n = 5; Console.WriteLine(minimum_apple(arr, n)); } public static int minimum_apple(int[] arr, int n) { Array.Sort(arr); int c = 1; for (int i = 1; i < n; i++) { if (arr[i - 1] != arr[i]) { c++; } } return c; }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
function minimum_apple(arr, n) { arr.sort(); let c = 1; for (let i = 1; i < n; i++) { if (arr[i - 1] !== arr[i]) { c++; } } return c;}const arr = [1, 1, 1, 1, 1];const n = 5;console.log(minimum_apple(arr, n)); |
1
Time Complexity: O(n*logn), because of sorting.
Auxiliary Space: O(1)
Method 2: To solve the problem follow the below idea:
As we can see answer will be the number of different persons in the array because every person will get atmost 1 kg apples.
- We can find out different persons by using hash map also .
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>;using namespace std;int minimum_apple(int arr[], int n){ // Using hashmap to find unique person unordered_map<int,int> mp; for(int i=0;i<n;i++){ mp[arr[i]] = 1; } return mp.size();}// Drivers codeint main(){ int arr[] = { 1, 1, 1, 2, 1 }; int n = 5; // Function Call cout <<minimum_apple(arr, n) << endl; return 0;} |
Java
import java.util.HashMap;public class GFG { // Function to find the minimum number of apples static int minimum_apple(int[] arr, int n) { // Create a HashMap to store the occurrences of elements in the array HashMap<Integer, Integer> mp = new HashMap<>(); // Count the occurrences of each element in the array for (int i = 0; i < n; i++) { mp.put(arr[i], 1); } // Return the size of the HashMap, which represents the number of distinct apples return mp.size(); } // Drivers code public static void main(String[] args) { int[] arr = {1, 1, 1, 2, 1}; int n = 5; // Function Call System.out.println(minimum_apple(arr, n)); }} |
Python
def minimum_apple(arr, n): # Using a dictionary to find unique person mp = {} for i in range(n): mp[arr[i]] = 1 return len(mp)# Driver codeif __name__ == "__main__": arr = [1, 1, 1, 2, 1] n = 5 # Function Call print(minimum_apple(arr, n)) |
C#
using System;using System.Collections.Generic;class Program{ // Function to find the minimum number of apples static int MinimumApple(int[] arr, int n) { Dictionary<int, int> mp = new Dictionary<int, int>(); // Count the occurrences of each element in the array for (int i = 0; i < n; i++) { mp[arr[i]] = 1; } return mp.Count; } static void Main(string[] args) { int[] arr = { 1, 1, 1, 2, 1 }; int n = 5; // Function Call Console.WriteLine(MinimumApple(arr, n)); }} |
Javascript
function minimum_apple(arr, n) { // Using map to find unique person let mp = new Map(); for (let i = 0; i < n; i++) { mp.set(arr[i], 1); } return mp.size;}// Drivers codelet arr = [1, 1, 1, 2, 1];let n = 5;// Function Callconsole.log(minimum_apple(arr, n)); |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
