# Equalize the Array

# Equalize the Array

grossman + 25 comments O(n) solution

public static int minDeletions(int[] a) { int max = 1; Map<Integer, Integer> nums = new HashMap<>(); for (int i : a) if (!nums.containsKey(i)) nums.put(i, 1); else { nums.put(i, nums.get(i) + 1); if (max < nums.get(i)) max = nums.get(i); } return a.length - max; }

itaravin + 0 comments Good Solution bro :)

Virta + 1 comment I used same solution. But maps seem to have log(n) complexity themselves too :()

grossman + 1 comment The worst case of maps time complexity is O(n), if it must iterate thru whole hashbucket. But usually it's O(1).

jacob_williams + 1 comment Isn't O notation only about worst case? If worst case is linear, it is O(n). O notation doesn't consider the most common time or the average time.

fortyseven05 + 0 comments Nah. Look up Big O amortized. The short answer is that, generally Big O is about worst case, but when that worst happens very rarely and it's expected that an algorithm will be faster, that's the one we go with. Good example (from Cracking the Coding Interview) is dynamic arrays . Say we were to initialize a dynamic array with size 1. Assigning a value to it is O(1). However, when the array is full - but we still want to add soemthing to it - it needs to be resized. In that case, a new array is created with double the size and the original array's contents are transferred over. When we do that, the time to add that second element becomes O(n) for that single operation. As we continue to add elements to the array, resizing it becomes less and less common. So the time to add an element to the array is O(1), amortized O(n)

FilipF + 0 comments Yup, nice! The solution can get a slight speed up by caching

`nums.get(i)`

instead of calling it three times. One could even replace`!.containsKey()`

with`cache == null`

.rudra_utpal + 3 comments import java.util.*; public class Solution { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int n=scan.nextInt(); ArrayList<Integer> al=new ArrayList<Integer>(); for(int i=0;i<n;i++) al.add(scan.nextInt()); HashSet<Integer> hs=new HashSet<Integer>(al); ArrayList<Integer> res=new ArrayList<Integer>(); for(Integer i : hs) res.add(Collections.frequency(al,i)); System.out.println(n-Collections.max(res,null)); } }

madking562 + 3 comments sir how do u know all these kinda things.i mean what concept you used please tell me sir.i wanna learn it...i can code only in terms of logical view in java.but you are simply solving by writing some methods... howw sirr..what should i learn to code like you

Steve__Jobs + 0 comments yeah..me too sir...

rudra_utpal + 0 comments Collections minimizes ur efforts . . . just learn the concepts behind collections and then with a little practise u 2 can code like this . . . it's not a big thing

mdunicorn + 0 comments Ream sum books about programming and algorithms! "Introduction to Algorithms" is highly recommended. Also read one or two books about programming in Java. There is no easy way bro! Put some effort for it.

Amyth07 + 1 comment why u have used hashset? -just to remove duplicate elemnts?

fortyseven05 + 0 comments I was wondering the same thing. He should have just use a hashtable. Using the ArrayList is going to have insertion time of O(n) for three of the first four elements added instead of O(1) for a hash table, never mind the unneccesary space taken by having a hashset and an arraylist

Anutrix + 1 comment A bit expanded but similar I guess.

import java.io.*; import java.util.*; import java.util.stream.IntStream; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] a = new int[n]; for(int a_i = 0; a_i<n; a_i++){ a[a_i] = in.nextInt(); } int max = 0; List<Integer> list = new ArrayList<Integer>(); for (int item : a) { list.add(item); } for(int item : a) { int frequency = Collections.frequency(list, item); max = Math.max(max, frequency); } System.out.println(n-max); } }

verma_shantanu17 + 1 comment [deleted]verma_shantanu17 + 0 comments Magically It Worked. Thanx A Similar Solution In Python 3:

`from collections import Counter def equalizeArray(arr): d=Counter(arr).values() deletion=len(arr)-max(d) return deletion`

KeyurPotdar + 1 comment [deleted]Amyth07 + 3 comments a[t]++ what does it means??

KeyurPotdar + 0 comments [deleted]Anutrix + 0 comments a[t] = a[t]+1;

gargankit476 + 0 comments It means we are incrementing the value in array a at t index. Like in array [1,2,3,4,1,2] after doing a[t]++ the a will be

a[0,2,2,1,1,0]

bloodaspayment + 1 comment The int size is 100, why not just use an array for O(1) look up?

davidvargash + 0 comments thats precisely my point. i solved it using an array on 100 positions as the input is only going to be in the range of 1 <= x <= 100.... ...this is an classic Counting Sort problem... static int EqualizeArray(int[] arr) { int max = 0; int[] d = new int[101]; for (int i = 0; i < arr.Length; i++) { d[arr[i]]++; if (d[arr[i]] > max) max = d[arr[i]]; }

`return arr.Length - max; }`

shreyas_m + 1 comment Similar to your solution but I didn't use the max variable. Instead of that I used Collection class to pull out the key having maximum count.

public static void main(String[] args) { Scanner sc = new Scanner (System.in); int n = sc.nextInt(); HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0;i < n;i++) { int num = sc.nextInt(); if (map.containsKey(num)) map.put(num, map.get(num) + 1); else map.put(num, 1); } System.out.println(n - Collections.max(map.values())); }

khaledyasser2002 + 0 comments Did the same thing but I was lazy and just used a 100 element array

agnivabasak1 + 4 comments can anyone say why this isn't working ,it seems to be correct according to me but except 3 test cases all fail due to wrong answer ,also when i self test this code works mostly for all types of input except at one instance it showed a result in negative ,could someone help me with it ,pls.

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int n,k,max; cin>>n; int arr[100]; cin>>k; arr[k-1]++; max = k-1; for(int i=1;i<n;i++) { cin>>k; arr[k-1]++ ; if(arr[k-1]>arr[max]) max = k-1; } cout<<n-arr[max] ; return 0; }

tejasdhagawkar01 + 1 comment Initialize your array to zero or put that in global scope.

agnivabasak1 + 1 comment Oh thanks a lot,i completely forgot about initializing the array :P .

itsrmani + 0 comments Each class variable, instance variable, or array component is initialized with a default value when it is created (Â§15.9, Â§15.10) [...] For type int, the default value is zero, that is, 0.

bhavgothadiya + 0 comments It's Not Correct Logic My dear

CSociety + 1 comment sort(arr.begin(),arr.end()); int count = 0, j = 0; for(int i = 1; i<arr.size(); i++){ if(arr[j] != arr[i]){ j++; count++; } } return count;

jabra98 + 0 comments It's quick on small containers, but really slow on large ones. The avg test case in your impl is about 3-4 times slower than this here https://www.hackerrank.com/challenges/equality-in-a-array/forum/comments/654848

Srivastavavir18 + 0 comments [deleted]

daiict_201712029 + 1 comment **SIMPLE O(N) One liner**`Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[101]; for(int i=0;i<n;i++) { arr[sc.nextInt()]++; } System.out.println(n-Arrays.stream(arr).max().getAsInt());`

h326827370 + 2 comments why the size of arr is 101?

itsrmani + 0 comments yeah...Because,as per the given constrain ,maximum size of array is 101 so that we have to inialize array with size of 101..if we reduce the size then,it may causes the error when we give the input element which beyond the limit contrain ..I hope u can understand my comment

dsouzasunny33 + 0 comments Lucky number

saxenakshitij + 0 comments Awesome!!

vs9617925319 + 0 comments public class Solution {

`// Complete the equalizeArray function below. static int equalizeArray(int[] arr) { Arrays.sort(arr); int[] temp=new int[arr[arr.length-1]+1]; for(int i=0;i<arr.length;i++){ temp[arr[i]]++; } Arrays.sort(temp); int result=arr.length-temp[temp.length-1]; return result; }`

CSociety + 0 comments In Cpp

sort(arr.begin(),arr.end()); int count = 0, j = 0; for(int i = 1; i<arr.size(); i++){ if(arr[j] != arr[i]){ j++; count++; } } return count;

Arviy + 2 comments One line of code:

def equalizeArray(arr): return len(arr) - max(Counter(arr).items(), key= operator.itemgetter(1))[1]

advaithsurya + 0 comments Can you please explain this piece of code? Nice Pythonics but what are we really getting at here?

pepoluan + 0 comments Why would you use

`.items()`

?`Counter`

is like a`dict`

, just get the`.values`

from collections import Counter def equalizeArray(arr): return len(arr) - max(Counter(arr).values())

youassassin + 0 comments My code takes advantage of the constraints. Straight O(n).

static int equalizeArray(int[] arr) { int max = 0; int [] x = new int[100]; //takes advantage of the fact that the values can be used to represent their index counterpart for(int i = 0; i < arr.length;i++) max = Math.max(max, ++x[arr[i]-1]); return arr.length - max; }

nguyen_h_l + 0 comments Great way to use HashMap bro. My solution is longer than you... first group and count all matching number and then get highest matched number... total number - highest match number

basillatif + 0 comments I don't understand what happens in the else statement....how does nums.put(i, nums.get(i)+1) work?

ljibajap + 0 comments Can you explain what max represent in this case, I am confuse also why you add nums.get(i) + 1?

Kanahaiya + 0 comments 100 % working code with video explanation -- All Test Case Passed..!!

Here is the video explanation of my solution in O(n) time -

any like, dislike, feedback or comment would be highly appreciated.

vinay999 + 0 comments Isn't it O nlogn complexity ? contains method is some kinda search so i believe it should be O(nlogn). Please correct me if i am wrong.

Thanks

superfive + 0 comments for(int i : a) nums.put(i, nums.get(i) + 1); O(n)... LOL

kevinmandalia + 0 comments I would have used an array to have constant space - we know the max size of the array would be 100

mohak_py + 0 comments Mine is better than yours from collections import Counter n=int(input()) lis=list(map(int,input().split())) z=Counter(lis) b=max(z.values()) res=n-b print(res)

guilherme_guini + 0 comments You don't need stored values, right? You need only get max value.

the_happy_hacker + 0 comments One-liner

def equalizeArray(arr): return len(arr) - max(arr.count(i) for i in arr)

B150028_Gazala + 4 comments There's a bug in the 'boilerplate' code of the main function provided for the C implementation. When I read the input using scanf, this test case passes.

For test case 9:

35 32 32 37 72 72 96 12 32 67 37 57 18 57 78 29 34 67 16 34 78 72 33 96 16 37 32 87 43 29 16 48 49 29

This is the error.

GDB trace: Reading symbols from solution...done. [New LWP 10157] Core was generated by `solution'. Program terminated with signal SIGSEGV, Segmentation fault. #0 __GI_____strtol_l_internal ( nptr=nptr@entry=0xa1 <error: Cannot access memory at address 0xa1>, endptr=endptr@entry=0x7ffd6aace890, base=base@entry=10, group=group@entry=0, loc=0x7f7f606fb420 <_nl_global_locale>) at ../stdlib/strtol_l.c:293 #0 __GI_____strtol_l_internal ( nptr=nptr@entry=0xa1 <error: Cannot access memory at address 0xa1>, endptr=endptr@entry=0x7ffd6aace890, base=base@entry=10, group=group@entry=0, loc=0x7f7f606fb420 <_nl_global_locale>) at ../stdlib/strtol_l.c:293 #1 0x00007f7f603713d2 in __strtol ( nptr=nptr@entry=0xa1 <error: Cannot access memory at address 0xa1>, endptr=endptr@entry=0x7ffd6aace890, base=base@entry=10) at ../stdlib/strtol.c:106 #2 0x0000000000400887 in main () at solution.c:59

# 2 0x0000000000400887 in main () at solution.c:59

sagarikashrote + 0 comments same with me

nawnaw011222 + 1 comment Mine too, I even rewrote my solution it still crush saying runtime error.

a_gomaa003 + 0 comments did anyone solve this problem?

uphwa98 + 0 comments Thank you for your information. I passed the tc with c++.

icefrogkute + 0 comments i have a runtime error with this test case even have only return code inside function!!!

christian_sloper + 4 comments n = int(input()) A = list(map(int, input().split())) print ( n - max( [ A.count(t) for t in set(A) ]) )

diego_amicabile + 3 comments in a similar way

print(n-collections.Counter(A).most_common()[0][1])

beckwithdylan + 0 comments ..exponentially faster, O(n), as opposed to just using count which is O(n^2) worst case

wilmer_henao + 0 comments It's not just a one-liner. It's a readable one-liner. Grrat job.

advaithsurya + 0 comments Finding the least occured elements and deleting them and making a count while doing that is the solution. Now to do that this way? Brilliant.

Nice sol Mr.

milindverma + 1 comment which language is this??

christian_sloper + 0 comments Python 3

alison_thaung + 1 comment Nice! I thought my Python3 code was short, but you managed to get it in one line. Here's my code:

most = max(set(a), key = a.count) print(sum(i != most for i in a))

tonghuixiang01 + 0 comments what does key = a.count do?

semikovmv + 2 comments My solution:

n = int(input()) arr = sorted(list(map(int,input().split()))) s = sorted(list(set(arr))) l = len(arr) m = k = 0 mx = 1 for e in s: for i in range(m,l): k += 1 if arr[i] != e: m = i k -= 1 break if k > mx: mx = k k = 0 print(l - mx)

chandan37shaw + 0 comments I love itteration approach but please make sure to give some hints to make it understandable for a begineer.

arjitg450 + 0 comments Your solution will be O(n**2). So its complexity is n**2. Try to make it atleast logn.

readytohackk + 6 comments c++ :)

int main() {int n,max=0,q; cin>>n; map<int,int>m; for(int i=0;i<n;i++){ cin>>q; m[q]++; if(m[q]>max) max=m[q]; } cout<<n-max; /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }

Kartik1607 + 2 comments Given the low size of max number input (100), you can use an array instead of map.

pankaj_pec + 0 comments yeah, i used one.

ayush_nishad + 1 comment Array will comsume more space. Map is for optimal solution!

jabra98 + 1 comment But then you have to search through the map to increment the key's value each iteration?

ayush_nishad + 0 comments yeah! it's space vs time, to save up space you have to sacrifice time or vice versa. My code uses min space complexity.

singhabhi4047 + 1 comment can anyone explain the meaning of m[q]++ ???

lvkhoa + 0 comments You are counting the frequency of the duplicated value. For example : with [1, 2, 3, 3, 3] you can create an array a[6] to store the frequency of each value in the range [0-5] m[3] ++ ; meaning it increases the counter of value 3 to 1.

positivedeist_07 + 1 comment Did exactly the same :P but I used array instead of map. So, the runtime here is O(1), right? We're just looking up the array.. Am i right here?

ashwanigupta30 + 1 comment no it is o(n) as the length of the array is the length of the input

georgthmnky + 0 comments You shouldn't have to iterate over the entire array if the array has 100 values. Just increment from zero as a number comes up and track the max and youll have O(1) time for lookup....if youre talking about input as well it is O(n) though

wanghaitang_ufl + 0 comments interesting. I didn't know that you can simply use m[q]++ directly before the element was inserted. Here is my solution: https://www.hackerrank.com/challenges/equality-in-a-array

Koushica_Bosadi + 0 comments can you explain how does this mapm; function?

hachimaki1 + 0 comments C++

int equalizeArray(vector <int> arr) { int n = arr.size(); int count[101] = {0}; int max = 0; for (int i = 0; i < n; i++) if (++count[arr[i]] > max) max = count[arr[i]]; return n - max; }

AKSaigyouji + 0 comments Good occasion to take a functional approach. C# with LINQ:

Console.ReadLine(); string[] numbers = Console.ReadLine().Split(' '); int countMostCommon = numbers.GroupBy(c => c) .Max(group => group.Count()); Console.WriteLine(numbers.Length - countMostCommon);

vincentg + 1 comment Using Python 3's Counter but without having to change inputs into integers.

from collections import Counter input() A = Counter(input().split()) print(sum(A.values()) - A.most_common(1)[0][1])

161b172 + 1 comment print(sum(A.values()) - A.most_common(1)[0][1]) i dont understand that line and what is use of counter.

vincentg + 1 comment A Counter takes a collection of objects, in this case the list of strings created by

`input().split()`

, and creates a dictionary in which keys are the objects and the values are the quantity of each object. The`most_common(n)`

method allows us to create a list of the`n`

most common objects.`A.most_common(1)[0][1]`

gives use the quantity of the most common element. Here's an example from the Python3 docs:>>> Counter('abracadabra').most_common(3) # doctest: +SKIP [('a', 5), ('r', 2), ('b', 2)]

`Counter`

has the nice property that it runs in`O(n)`

time so it's pretty much the fastest way to count occurances of an object from any iterable.161b172 + 0 comments thanks

asmitat19 + 5 comments int main() { int n,i,j,max=0,cnt; scanf("%d",&n); int a[n]; for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n;i++) { cnt=0; for(j=0;j<n;j++) { if(a[i]==a[j]) cnt++; } if(cnt>max) max=cnt; } printf("%d",n-max); /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }

mittalria16 + 0 comments nice solution

saifulcseng + 0 comments your solution is nice but you can start j with j=i to reduce time. No need to find exact value of count if it is counted previosuly.

rakeshstonner + 0 comments It has nested loop. time complexity is O(nÂ²)

sriramsundaram91 + 0 comments O(n^2) complexity

rajeshpeddikuppa + 0 comments good one man

Riya_R + 0 comments C++:

int equalizeArray(vector<int> v) { sort(v.begin(),v.end()); vector<int> w; int p = v.size(); for(int i=0;i<p;){ int a = count(v.begin(), v.end(), v[i]); w.push_back(a); i=i+a; } int max = *max_element(w.begin(), w.end()); return p-max; }

f2015712 + 2 comments Count the element with maximum frequency and all other elements must be removed apart from that. from collections import Counter n=int(raw_input())

array=Counter(map(int,raw_input().split())) a=[] a=Counter(array).values() print(n-max(a))

Argooni + 0 comments Or another way with Counter:

print(len(i)-int(Counter(i).most_common(1)[0][1]))

mr_abedi + 3 comments it's easy to solve with python even without counter() :

arr=list(map(int,input().split())) print(len(arr)-max([arr.count(i) for i in arr]))

ricky03cool + 0 comments replace the len(arr) with n print(n-max([arr.count(i) for i in arr]))

calJersey + 0 comments does this work even if there are more than value that appear the maximum number of times? example: 1,2,3,5,3,5,3,5,4,1

askarovdaulet + 0 comments Good) Just be aware that this solution is O(n^2).

Sort 708 Discussions, By:

Please Login in order to post a comment