CODEWITHSUNDEEP
javascriptarrayssortingnumbers
HappyHands31
HappyHands31

Reputation: 4101

Find The Smallest - Codewars Challenge - Javascript

Trying to solve this Codewars challenge.

You have a positive number n consisting of digits. You can do at most one operation: Choosing the index of a digit in the number, remove this digit at that index and insert it back to another or at the same place in the number in order to find the smallest number you can get.

Task: Return an array or a tuple or a string depending on the language (see "Sample Tests") with:

1) the smallest number you got

2) the index i of the digit d you took, i as small as possible

3) the index j (as small as possible) where you insert this digit d to have the smallest number.

Example:

smallest(261235) --> [126235, 2, 0] or (126235, 2, 0) or "126235, 2, 0"

Other examples: 

209917, [29917, 0, 1]
285365, [238565, 3, 1]
269045, [26945, 3, 0]
296837, [239687, 4, 1]

So, in order to get the smallest number possible, we will want to remove the smallest digit from the number and place it at the front of the number, correct? 

function smallest (n) {
  //turn n into an array
  let array = String(n).split("").map(Number);
  
  let smallest = Math.min(...array);
  
  //find index of smallest in original array
  let index = array.indexOf(smallest);
  
  //remove smallest from original array, move it to front
  array.splice(index, 1);
  array.unshift(smallest);
  let newNumber = Number(array.join(""));

  //return array of new number, index of where the smallest was, 
  //and index of where the smallest is now
  return ([newNumber, index, 0]);
}
console.log(smallest(239687));

My answer is returning the correct number, but, about half the time, it is not returning the correct index i and index j.

EDIT: Latest attempt:

function smallest (n) {

  let array = Array.from(String(n)).map(Number);
  let original = Array.from(String(n)).map(Number);
  let sorted = Array.from(String(n)).map(Number).sort((a, b) => a - b);

  let swapValueOne = [];
  let swapValueTwo = [];

  for (let i = 0; i < array.length; i++) {
    if (array[i] !== sorted[i]) {
      swapValueOne.push(sorted[i]);
      swapValueTwo.push(original[i]);
      break;
    }
  }

  swapValueOne = Number(swapValueOne);
  swapValueTwo = Number(swapValueTwo);
  
  let indexOne = original.indexOf(swapValueOne);
  let indexTwo = original.indexOf(swapValueTwo);

  //remove swapValue
  array.splice(indexOne, 1);
  //insert swapValue
  array.splice(indexTwo, 0, swapValueOne);

  return ([Number(array.join("")), indexOne, array.indexOf(swapValueOne)]);

}

console.log(smallest(296837));

^ Sometimes it gives the correct number with the correct swap indices, and sometimes both the number and the swap indices are wrong.

Upvotes: 2

Views: 2470

Answers (3)

Dario Fabian
Dario Fabian

Reputation: 11

The approach of finding the first not sorted element doesnt solve correctly all the cases for example if the number is 300200, the first not sorted number is the 3 and if you put a 0 in that place, depending what 0 you move you got:

(0)30020 (0)30020 (0)30200 (0)30200

All of the answers are wrong because what you have to do is to put the 3 at the end of the number to get

(000)2003

Upvotes: 1

Mark
Mark

Reputation: 92440

Here's a small idea that might help.

If you have a number like:

239687

The smallest number you can make with this is the sorted digits:

236789

In the original number, the 2 and the 3 are already in the correct position. If you start from the left of the number and the sorted number, the first difference you find is the number that needs to be swapped. It needs to be swapped with the corresponding number in the sorted list:

orig   2 3 9 6 8 7 -- 6 needs to go before 9
       | | x       
sorted 2 3 6 7 8 9

Above the next sorted digit is 6, but the original has 9. You need to insert 6 before 9.

For an algorithm you can sort your digits and find the index of the first difference (starting from the left). This is one of your return values (2 in the example). Now find the index of sorted[2] (ie. 6) in the original (index 3). Insert the value in you original array and you're done.

Upvotes: 1

ggorlen
ggorlen

Reputation: 56993

Putting the smallest element in the front (let's call it a "greedy" solution) is non-optimal. Consider the case where n = 296837, as in your last test case. Your code returns [296837, 0, 0] because it finds that 2 is the smallest digit and it moves it to the front (does nothing, essentially). As your example illustrates, there's a better approach: [239687, 4, 1], that is, move 3 to the first index in the array.

You'll need to reformulate your strategy to be non-greedy to find a global optimum.

If you're still stuck, you can try the following:

Numbers can't contain that many digits--why not try every possible swap?

Upvotes: 2

Related Questions