Cut the sticks: Hackerrank warmup challenge

Question

I've been trying to solve the warmup challenges on Hackerrank. For this particular challenge - https://www.hackerrank.com/challenges/cut-the-sticks - I've written some code, and although it seems logically correct to me, I'm not getting the right answer.

My Code -

import java.util.*;

public class Solution {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int lengths[] = new int[n];
        List<Integer> output = new LinkedList<Integer>();

        for (int i = 0; i < n; i++)
            lengths[i] = sc.nextInt();

        sc.close();
        Arrays.sort(lengths);

        for (int i = 0; i < n; i++) {
            if (lengths[i] == 0)
                continue;
            else {
                output.add(n - i);
                for (int j = i; j < n; j++) {    // This loop isn't working like it should
                    lengths[j] -= lengths[i];
                 // System.out.print(lengths[j] + " ");  // For debugging purposes
                }
             // System.out.println("");
            }
        }

        for (int i = 0; i < output.size(); i++)
            System.out.println(output.get(i));
    }
}

For the following input -

6
5 4 4 2 8 2

The output I get is -

6
5
4
3
2
1

The correct output should be -

6
4
2
1

I tried to display the values of the lengths array throughout the runs of the for loop marked in the code (with a comment), and this is what i get for the same inputs as above -

0 2 4 4 5 8 
0 4 4 5 8 
0 4 5 8 
0 5 8 
0 8 
0 
6
5
4
3
2
1

I'm totally stumped as to why this would happen.

Answer 1

The problem is here:

lengths[j] -= lengths[i];

When i == j is true, this changes the value of lengths[i]. You need to save that value first.

 final int v = lengths[i];
 for (int j = i; j < n; j++) {
     lengths[j] -= v;
 }

Answer 2

Had solved it sometime back.

Here's a version of answer, using a do while loop

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int size = scan.nextInt();
    int sticks [] = new int[size];
    for (int i = 0; i < size; i++){
        sticks[i] = scan.nextInt();
    }    
    Arrays.sort(sticks);
    do {
    int count =0;
    int leastLength = sticks[0];
    for (int j=0; j < sticks.length; j++){
        sticks[j] = sticks[j] - leastLength;
        count++;
    }
    System.out.println(count);
    List<Integer> resizeArray = new LinkedList<Integer>();
    for ( int i=0; i< sticks.length; i++){
        if (sticks[i] != 0){
            resizeArray.add(sticks[i]);
        }
    }
    int temp[] = new int[resizeArray.size()];
      for (int i = 0; i < resizeArray.size(); i ++){
          temp[i] = resizeArray.get(i);
      }
      sticks = temp;
    } while (sticks.length > 0);
}

Answer 3

  package com.omt.learn.algo;

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Arrays;

  public class CutTheSticks2 {
    public static void main(String s[]) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        short N = Short.parseShort(br.readLine());
        short[] A = new short[N];
        N = 0;
        for (String str : br.readLine().split(" ")) {
            A[N++] = Short.parseShort(str);
        }

        Arrays.sort(A);

        StringBuffer sb = new StringBuffer();
        System.out.println(N);
        for (int i = 1; i < N; i++) {
            if (A[i - 1] != A[i]) {
                sb.append((N - i) + "\n");
            }
        }

        // OUTPUT
        System.out.print(sb);
    }
  }

Answer 4

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int arr[] = new int[n];
        for(int arr_i=0; arr_i < n; arr_i++){
            arr[arr_i] = in.nextInt();
        }
        int count = 2;
        int min=1000;
        for(int arr_i=0;count !=1 ; arr_i++){ // read
            count = 0;
            for(int arr_j=0; arr_j < n; arr_j++)// find min
            { if(min >arr[arr_j] && arr[arr_j]!=0)
               min=arr[arr_j];
              }

            for(int arr_k=0; arr_k < n; arr_k++)// sub
            {
                if(arr[arr_k]>=min)
                 {   count++;
                     arr[arr_k]= arr[arr_k] - min;
                 }


            }

           System.out.println(count);  
        }

    }
}

Answer 5

This is a working solution in JavaScript. Took me a while to realize that the sort() in JavaScript performs a string comparison in alphabetical order.

function sortNumbers(a, b) {
    return a - b;
}

function cutSticks(arr){
    var smallestStick = 0;  
    arr = arr.sort(sortNumbers); 
    while(arr.length > 0) {
        console.log(arr.length);
        smallestStick = arr[0];

        var newArray = [];
        arr.forEach(function (val) {
            var newValue = val - smallestStick;
            if (newValue > 0) {
                newArray.push(newValue);
            }
        });

        arr = newArray;
    }
}

function main() {
    var n = parseInt(readLine());
    arr = readLine().split(' ');
    arr = arr.map(Number);
    cutSticks(arr);
}

Hope it helps!

Answer 6

Java Version. Passed all tests, but not sure if is best performance.

static int[] cutTheSticks(int[] arr) {

    List<Integer> sticks = Arrays.stream(arr).boxed().collect(toList());
    List<Integer> cuts = new ArrayList<>();

    while (true) {
        int min = sticks.stream().mapToInt(Integer::valueOf).min().getAsInt();
        Iterator it2 = sticks.iterator();
        int cuted = 0;
        List<Integer> temp = new ArrayList<>();
        while (it2.hasNext()) {
            int v = (int) it2.next();
            if (v == min) {
                it2.remove();
                cuted++;
            } else {
                int nv = v - min;
                it2.remove();
                temp.add(nv);
                cuted++;
            }
        }
        cuts.add(cuted);
        sticks.addAll(temp);
        if (sticks.isEmpty()) {
            break;
        }
    }
    return cuts.stream().mapToInt(Integer::valueOf).toArray();
}