Greedy Algorithm with Maximum Salary Problem?-CodePudding

I am trying to solve the below problem. I think my solution is working well. But, the system in which I am trying to upload the solutions, is not accepting my solution. Probably some tests are failing. May I know what am I missing?

The problem is:

As the last question of a successful interview, your boss gives you a few pieces of paper with numbers on it and asks you to compose a largest number from these numbers. The resulting number is going to be your salary, so you are very much interested in maximizing this number. How can you do this?

Sample 1

Input:

2

21 2

Output: 221

Sample 2

Input:

3

23 39 92

Output: 923923

My solution is:

function MaxSallary(nums) {
  let maxSize = Math.max(...nums).toString().length;
  let newArr = [];

  nums.map((num) => {
    while (num.toString().length < maxSize) {
      num = num.toString().concat(num.toString().split("").slice(-1)[0]);
    }

    newArr.push(Number(num));
  });

  finalArr = [];
  while (newArr.length > 0) {
    let minIndex = newArr.indexOf(Math.max(...newArr));
    newArr.splice(minIndex, 1);
    finalArr.push(...nums.splice(minIndex, 1));
  }
  return finalArr.join("");
}

console.log(MaxSallary([2, 12, 34, 11, 43, 21, 5]));

CodePudding user response：

You want to know in which order the numbers should be concatenated, so that, once parsed back to a number, the result is the highest possible. Reworded this way, it looks like we should sort the array first.

When comparing two numbers a and b, to know which one should come first, we need to know which one is higher between ${a}${b} and ${b}${a}:

.sort((a, b) => parseInt(`${b}${a}`, 10) - parseInt(`${a}${b}`, 10)))

.sort mutates the array (and returns it), so I'm cloning it first.

function MaxSallary(nums) {
  const salary = [...nums]
    .sort((a, b) => parseInt(`${b}${a}`, 10) - parseInt(`${a}${b}`, 10))
    .join("");
  return salary;
}

console.log(MaxSallary([21, 2]));
console.log(MaxSallary([23, 39, 92]));
console.log(MaxSallary([2, 12, 34, 11, 43, 21, 5]));