2

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.

Improve this question
2
  • 1
    The second test looks to be incorrect. testing(209917, [29917, 0, 1]); But the found index should be 1, and it should be inserted at index 0 Commented Jun 25, 2019 at 2:07
  • The description specifies "[29917, 1, 0] could be a solution too but index i in [29917, 1, 0] is greater than index i in [29917, 0, 1].", so there's a way to disambiguate this. Commented Jun 25, 2019 at 2:13

3 Answers 3

Reset to default
2

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?

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Okay so you could create an array of arrays of all possible combinations, then sort them to find the smallest value, and then determine what swaps need to take place in order to arrive at that value....(?)
You might be overthinking it. Sorting isn't necessary to find the smallest value, and we can safely ignore the smallest value anyway and just brute force it. If we have a 10-digit number, say, how many possible indices i and j can we swap (including i == j)? The largest safe integer in JS is only 16 digits, so a quadratic solution is plenty quick (less than 150 iterations). There are further optimizations, but starting with this is sufficient to solve the problem naively, which should always be your first thought in coding challenges.
1

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.

Improve this answer

3 Comments

So in my edit I've added a snippet for getting the first difference starting from the left - is that correct?
Yeah, that looks reasonable to me. There is also findIndex(), which is a little shorter.
Please see my most recent attempt. There are times when the number is right, but the indexes are wrong, and there are times when everything is wrong. Maybe there is something wrong with the way I'm inserting (swapping) the values in the original array, I'm not sure.
1

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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.