Importance of Mathematical intuition!

complex_and_buggy.py

def main():
	n,m=map(int,raw_input().rstrip().split(' '))
	

	a=map(int,raw_input().rstrip().split(' '))   # a[i] -> song number i+1

	# make the array b where b[j] -> number of songs grp j is performing
	b=[]
	for i in xrange(m+1):
		b.append(0)

	changes = 0		# minimum number of changes

	# KEY IDEA : at the end, all songs to be played by 1 to m
	# Question : How to keep track of the changed list
	# idea : ? - make a dictionary of bands 1->m, and songs from 1->n as dictionary for each!

	bands_dict={}
	for i in xrange(m+1):
		bands_dict[i]={}

	for i in xrange(n):
		if a[i]<=m:
			bands_dict[ a[i] ][ i+1 ] = 1
			b[ a[i] ] +=1
		else:
			bands_dict[0][i+1]=1
			b[0]+=1


	# debug
	# print b 	
	# print bands_dict

	# empty b[0]
	min_index=1			# min_index -> band
	min_value=b[1]		# min_value -> number of songs played by the band

	prev_min_index=-1
	prev_min_value=-1
	prev_replaced_song=-1

	print b

	flag=0
	while b[0]>0:

		'''
		not working for the edge case
		5 4
		3 1 49598 52227 762868
		'''

		# we don't need to empty b[0], use prev min here too to break the loop!

		# find minimum from b[1] to b[m]
		for i in xrange(1,m+1):
			if b[i]<=min_value:
				min_index=i
				min_value=b[i]


		# stopping condition, to reverse the stuff
		
		if flag==1:
			if min_value<=prev_min_value and min_value!=0:

				bands_dict[0][ prev_replaced_song ]=1  			# to_replace song added in the band min_index
				bands_dict[prev_min_index].pop(prev_replaced_song)  			# to_replace song deleted from the band 0 (others)

				b[0]+=1
				b[prev_min_index]-=1

				changes-=1
				break
		


		# place 1 value from b[0] to b[min_index]
		# ? - which song?!
		replaced_song = bands_dict[0].keys()[0]   # song to be replaced

		bands_dict[min_index][ replaced_song ]=1  	# to_replace song added in the band min_index
		bands_dict[0].pop(replaced_song)  			# to_replace song deleted from the band 0 (others)

		b[min_index]+=1
		b[0]-=1

		changes += 1

		flag=1

		prev_replaced_song=replaced_song
		prev_min_index=min_index
		prev_min_value=min_value


	# keep on finding max & min, doing the replacements
	# until we reach the stable state


	# looping on till we find the stable state!
	flag=0						# first time
	prev_replaced_song = -1   	# first time
	prev_min_index=-1
	prev_max_index=-1

	prev_min_value=-1
	prev_max_value=-1


	print b
	while b[0]==0:

		min_index=1
		max_index=1

		min_value=b[1]
		max_value=b[1]


		for i in xrange(1,m+1):
			if min_value>=b[i]:
				min_index=i
				min_value=b[i]

			if max_value<=b[i]:
				max_index=i
				max_value=b[i]


		# stopping condition, to reverse the stuff

		if flag==1:
			if min_value<=prev_min_value:

				bands_dict[prev_max_index][ prev_replaced_song ]=1  			# to_replace song added in the band min_index
				bands_dict[prev_min_index].pop(prev_replaced_song)  			# to_replace song deleted from the band 0 (others)

				b[max_index]+=1
				b[min_index]-=1

				changes-=1
				break


		if min_index==max_index:
			prev_min_index=min_index
			prev_max_index=max_index

			prev_min_value=min_value
			prev_max_value=max_value

			break



		replaced_song = bands_dict[max_index].keys()[0]   	# song to be replaced

		bands_dict[min_index][ replaced_song ]=1  			# to_replace song added in the band min_index
		bands_dict[max_index].pop(replaced_song)  			# to_replace song deleted from the band 0 (others)

		b[min_index]+=1
		b[max_index]-=1

		changes+=1
		prev_replaced_song = replaced_song

		prev_min_index=min_index
		prev_max_index=max_index

		prev_min_value=min_value
		prev_max_value=max_value


		flag=1		# other times!



	# maximum possible value of minimum -> prev_min_value
	# minimum number of changes -> changes

	print prev_min_value, changes

	new_a=[]
	for i in xrange(n+1):
		new_a.append(0)

	for key in bands_dict:
		for elm in bands_dict[key]:
			new_a[elm]=key

	for i in xrange(0,n+1):
		print new_a[i],
	print



if __name__=='__main__':
	main()

simple_and_intuitive.py

def main():
	n,m=map(int,raw_input().rstrip().split(' '))
	a=map(int,raw_input().rstrip().split(' '))

	ls=[]
	for i in range(m+1):
		ls.append([])

	for i in range(n):
		if a[i]>m:
			ls[0].append(i+1)
		else:
			ls[ a[i] ].append(i+1)


	for i in range(1,m+1):
		while len(ls[i])>(n/m):
			elm=ls[i].pop()
			ls[0].append(elm)


	changes=0
	for i in range(1,m+1):
		while len(ls[i])<(n/m):
			elm=ls[0].pop()
			ls[i].append(elm)
			a[elm-1]=i
			changes+=1


	print n/m, changes
	for elm in a:
		print elm,
	print 



if __name__=='__main__':
	main()