Algorithm : Sort an array according to digit root


In this problem, a given Integer array should be sorted based on their digit roots. Digit root of a positive number is defined as the sum of all its digits.

Ex:-
A=[ 2, 4, 12, 13, 24, 32]
Consider array 'A', Digit root array of array 'A' would be [ 2, 4, 3, 4, 6, 5]
After sorting that array according to digit root of integers result would be like,
 A=[ 2, 12, 4, 13, 32, 24]
Steps to solve

  1. Find digit root of each integer. More details of how to find the digit root of a positive integer can be obtained from my previous post about finding digit root .
  2. After finding the digit roots of numbers next thing has to be done is sort the integers in given array based on their digit roots.

For understand this solution you should have a good understand about Array sort() method in JavaScript and creating objects in JavaScript.

Here is the final solution for sort an integer array based on their digit roots using JavaScript.

function digitRootSort(a) { 
 var digitRoot = function(n) { 
  var root = 0; 
  while (n > 0) { 
   root += n ; 
   n = Math.floor(n / 10); 
  } return root; 
 } var buckets = {}; 

 for (var i = 0; i < a.length; i++) { 
  var root = digitRoot(a[i]); 
  if (!buckets[root]) { 
   buckets[root] = []; 
  } 
  buckets[root].push(a[i]); 
 } 

 var b = []; 
 for (var root in buckets) { 
  var bucket = buckets[root]; 
  bucket.sort(function (a, b) { return a - b; }); 
  for (var i = 0; i < bucket.length; i++) { 
   b.push(bucket[i]); 
  } 
 } 
 return b; 
}


If you have any problem or optimized solution even in another programming language. :)

No comments:

Post a Comment