-
-
Save Nicknyr/725163efc5c3da0d2ca59609bac4cdc1 to your computer and use it in GitHub Desktop.
/* | |
Ratiorg got statues of different sizes as a present from CodeMaster for his birthday, each statue having an non-negative integer size. Since he likes to make things perfect, he wants to arrange them from smallest to largest so that each statue will be bigger than the previous one exactly by 1. He may need some additional statues to be able to accomplish that. Help him figure out the minimum number of additional statues needed. | |
Example | |
For statues = [6, 2, 3, 8], the output should be | |
makeArrayConsecutive2(statues) = 3. | |
Ratiorg needs statues of sizes 4, 5 and 7. | |
*/ | |
function makeArrayConsecutive2(statues) { | |
let statuesNeeded = 0; | |
// Sort array smallest to largest | |
statues.sort((a, b) => { | |
return a - b; | |
}) | |
// Iterate through array and find gaps in values | |
for(let i = 0; i < statues.length; i++) { | |
// If there is a gap between neighboring numbers subtract higher number from lower number i.e. [3, 6] is 6 - 3. There is a gap of 3, so 2 numbers are missing i.e. 4, 5 | |
if(statues[i + 1] - statues[i] > 1) { | |
statuesNeeded += statues[i + 1] - statues[i] - 1; | |
} | |
} | |
return statuesNeeded; | |
} |
Python Solution
def solution(statues):
statues.sort()
statuesNeeded = 0
for i in range(0, len(statues)-1):
if(statues[i + 1] - statues[i]) > 1:
statuesNeeded = statuesNeeded + statues[i + 1] - statues[i] - 1
print(f'Status needed {statuesNeeded}')
return statuesNeeded
Golang Solution
import (
"sort"
"fmt"
)
func solution(statues []int) int {
statuesNeeded := 0
sort.Ints(statues)
for i := 0; i < len(statues) - 1 ; i++ {
if statues[i+1] - statues[i] > 1 {
statuesNeeded += statues[i+1] - statues[i] - 1
}
}
fmt.Println(statuesNeeded)
return statuesNeeded
}
I didn't find a need to iterate further beyond the initial sort: Javascript solution, just submitted this, works fine.
statues.sort((a, b) => a-b, 0);
let max = statues[statues.length - 1];
let min = statues[0];
let diff = max - min;
return diff - statues.length + 1;
The key to this is that no tests have duplicates in the data set. So after sorting you already know the maximum value (last index), minimum value (first index) and that the total number of indexes should be the difference between those.
I got different solution. It might not be the best, however, I am very proud of this solution since I brainstorm from the start to finish.
int solution(int[] statues) {
/*
[6,2,3,8]
[2,3,,,6,_,8]
0 1 2 3 4 5 6
array size: n+1 =7
given: 4
[4 5 2 1]= 4
[1,2,_,4,5] = n+1=5
0,1,2,3,4
*/
int min = statues[0];
int max = statues[0];
int len,ans;
for(int i=0;i<statues.length;i++){
if(statues[i]<min){
min= statues[i];
}
if(statues[i]>max){
max=statues[i];
}
}
System.out.println(max);
System.out.println(min);
len = (max-min)+1;
ans= len-statues.length;
return ans;
}
def solution(statues): return(max(statues)-min(statues)+1-len(statues))
same as adel3li
function solution(statues) {
const min = Math.min(...statues)
const max = Math.max(...statues)
const dist = max-min+1
const spacing=statues.length
return dist-spacing
}
java version working :
boolean solution(int[] sequence) {
// [1, 2, 1, 2]
// i-2, i-1, i, i+1
// Stores the count of numbers that are needed to be removed
int count = 0;
// Store the index of the element that needs to be removed
int index = -1;
// Traverse the range [1, N - 1]
for(int i = 1; i < sequence.length; i++)
{
// If arr[i-1] is greater than or equal to arr[i]
if (sequence[i - 1] >= sequence[i])
{
// Increment the count by 1
count++;
// Update index
index = i;
}
}
// If count is greater than one
if (count > 1)
return false;
// If no element is removed
if (count == 0)
return true;
// If only the last or the first element is removed
if (index == sequence.length - 1 || index == 1)
return true;
// If a[index] is removed
if (sequence[index - 1] < sequence[index + 1])
return true;
// If a[index - 1] is removed
if (index - 2 >= 0 && sequence[index - 2] < sequence[index])
return true;
// if there is no element to compare
if(index < 0)
return true;
return false;
}
Javascript version
I used javascript to solve the problem, I used reduce to calculate the minimum number of additional statues in a single line.
The reduction function checks the difference between each pair of adjacent statues and accumulates these differences into a total.
function solution(statues) {
statues.sort((a, b) => a - b);
return statues.reduce((total, current, index, array) => index < array.length - 1 ? total + array[index + 1] - current - 1 : total, 0);
}
Here is another logic, a l'll different but works all good
Javascript
function solution(statues) {
var statues1 = statues.sort((a,b) => {
return a-b;
});
console.log(statues1.valueOf());
const L = statues[0];
const R = statues[statues.length-1];
var count = 0;
for (var i=L;i<=R;i++){
if(statues.includes(i)==false){
count = count + 1;
}
}
return count;
}
C# Solution
` int solution(int[] statues)
{
}`
When you calculate the difference between the values and you take off 1 you'll have how much numbers should be in the middle.
For example:
[2,5,6]
if you do: 5-2 = 3
3 is the difference but you need the quantity of the numbers in the middle of the difference which means that you can't include the number 5, so you just take it off (3-1 = 2) and then you keep the result in a variable (n in my case) .
That is what this line means:
n = n + statues[i+1] - statues[i]-1;