Make_Array_Consecutive_2.md

🔷 Shape Area Challenge

Challenge description

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
solution(statues) = 3.

Ratiorg needs statues of sizes 4, 5 and 7.

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] array.integer statues

  An array of distinct non-negative integers.

  Guaranteed constraints:
  1 ≤ statues.length ≤ 10,
  0 ≤ statues[i] ≤ 20.

• [output] integer

  The minimal number of statues that need to be added to existing statues such that it contains every integer size from an interval [L, R] (for some L, R) and no other sizes.

Solutions:

• JS solution

  CodeSignalSolutions/Make_Array_Consecutive_2/Make_array_consecutive_2.js

  Lines 1 to 25 in 5832427

  	function solution(statues){
  	let neededStatues = 0
  	for(var i = 1, max= statues[0], min = statues[0]; i<statues.length; i++){
  	let current = statues[i];
  	if(statues.indexOf(current)!=i)
  	continue;
  	if(current > max){
  	neededStatues += current - max - 1
  	max = current
  	}else if(current < min){
  	neededStatues += current - min -1
  	min = current
  	}else {
  	neededStatues--
  	}
  	}
  	return neededStatues
  	}
  	let test = [0, 9, 6, 6, 5, 5, 1]
  	let test1 = [1]
  	console.log(`You need ${solution(test)} more statues to have all sizes from [${test}]`)
  	console.log("You need %d more statues to have all sizes from %s", solution(test1), test1)

  

• Java solution

  CodeSignalSolutions/Make_Array_Consecutive_2/Make_array_consecutive_2.java

  Lines 1 to 29 in d1912aa

  	import java.util.Arrays;
  	import java.util.ArrayList;
  	class Make_array_consecutive_2{
  	public static void main(String args[]){
  	int [] test = {6, 6, 6, 2, 3, 8}, test2 = {5, 4, 6};
  	System.out.format("To have all sizes from %s Ratiorg needs %d additional statues %n", Arrays.toString(test), solution(test));
  	System.out.format("To have all sizes from %s Ratiorg needs %d additional statues %n", Arrays.toString(test2), solution(test2));
  	}
  	static int solution(int[] sizes){
  	ArrayList<Integer> neededStatues = new ArrayList<>();
  	for(int i = 1, max = sizes[0], min = sizes[0]; i < sizes.length; i++){
  	int current = sizes[i];
  	if(neededStatues.remove(Integer.valueOf(current)))
  	continue;
  	if(current > max){
  	while (++max < current)
  	neededStatues.add(max);
  	max = current;
  	} else if(current < min){
  	while(--min > current)
  	neededStatues.add(min);
  	min = current;
  	}
  	}
  	System.out.format("Needed statues: %s%n", neededStatues);
  	return neededStatues.size();
  	}
  	}

  

• Java Arrays API solution

  CodeSignalSolutions/Make_Array_Consecutive_2/MakeArrayConsecutive2.java

  Lines 1 to 18 in aed58da

  	import java.util.Set;
  	import java.util.Arrays;
  	import java.util.stream.Collectors;
  	public class MakeArrayConsecutive2{
  	public static void main (String args[]){
  	int[] test = {0, 9, 6, 6, 5, 5, 1};
  	int[] test1 = {0};
  	System.out.format("You need %d more statues to have all consecutive sizes from %s%n", solution(test), Arrays.toString(test));
  	System.out.format("You need %d more statues to have all consecutive sizes from %s%n", solution(test1), Arrays.toString(test1));
  	}
  	static int solution(int[] statues){
  	Set<Integer> sizes = Arrays.stream(statues).boxed().collect(Collectors.toSet());
  	int max = sizes.stream().max(Integer::compareTo).get(),
  	min = sizes.stream().min(Integer::compareTo).get();
  	return (max - min + 1) - sizes.size();
  	}
  	}