Count frequencies of all elements in array in O ( 1 ) extra space and O ( n ) time | Function to find counts of all elements present in arr [ 0. . n - 1 ] . The array elements must be range from 1 to n ; Traverse all array elements ; If this element is already processed , then nothing to do ; Find index corresponding to this element For example , index for 5 is 4 ; If the elementIndex has an element that is not processed yet , then first store that element to arr [ i ] so that we don 't lose anything. ; After storing arr [ elementIndex ] , change it to store initial count of 'arr[i]   ; If this is NOT first occurrence of arr [ i ] , then decrement its count . ; And initialize arr [ i ] as 0 means the element ' i + 1' is not seen so far ; Driver program to test above function
def findCounts ( arr , n ) : NEW_LINE INDENT i = 0 NEW_LINE while i < n : NEW_LINE INDENT if arr [ i ] <= 0 : NEW_LINE INDENT i += 1 NEW_LINE continue NEW_LINE DEDENT elementIndex = arr [ i ] - 1 NEW_LINE if arr [ elementIndex ] > 0 : NEW_LINE INDENT arr [ i ] = arr [ elementIndex ] NEW_LINE arr [ elementIndex ] = - 1 NEW_LINE DEDENT else : NEW_LINE INDENT arr [ elementIndex ] -= 1 NEW_LINE arr [ i ] = 0 NEW_LINE i += 1 NEW_LINE DEDENT DEDENT print ( " Below ▁ are ▁ counts ▁ of ▁ all ▁ elements " ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT print ( " % d ▁ - > ▁ % d " % ( i + 1 , abs ( arr [ i ] ) ) ) NEW_LINE DEDENT print ( " " ) NEW_LINE DEDENT arr = [ 2 , 3 , 3 , 2 , 5 ] NEW_LINE findCounts ( arr , len ( arr ) ) NEW_LINE arr1 = [ 1 ] NEW_LINE findCounts ( arr1 , len ( arr1 ) ) NEW_LINE arr3 = [ 4 , 4 , 4 , 4 ] NEW_LINE findCounts ( arr3 , len ( arr3 ) ) NEW_LINE arr2 = [ 1 , 3 , 5 , 7 , 9 , 1 , 3 , 5 , 7 , 9 , 1 ] NEW_LINE findCounts ( arr2 , len ( arr2 ) ) NEW_LINE arr4 = [ 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 3 ] NEW_LINE findCounts ( arr4 , len ( arr4 ) ) NEW_LINE arr5 = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 ] NEW_LINE findCounts ( arr5 , len ( arr5 ) ) NEW_LINE arr6 = [ 11 , 10 , 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 ] NEW_LINE findCounts ( arr6 , len ( arr6 ) ) NEW_LINE