Cut the sticks Hackerrank problem solution

                                     Cut the sticks Hackerrank

Cut the sticks Hackerrank

You are given N sticks, where the length of each stick is a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the smallest stick.

Suppose we have six sticks of the following lengths:

5 4 4 2 2 8
Then, in one cut operation we make a cut of length 2 from each of the six sticks. For the next cut operation four sticks are left (of non-zero length), whose lengths are the following:

3 2 2 6
The above step is repeated until no sticks are left.

Given the length of N sticks, print the number of sticks that are left before each subsequent cut operations.

Note: For each cut operation, you have to recalculate the length of smallest sticks (excluding zero-length sticks).

Input Format
The first line contains a single integer N.
The next line contains N integers: a0, a1,…aN-1 separated by space, where ai represents the length of the ith stick.

Output Format
For each operation, print the number of sticks that are cut, on separate lines.

Constraints
1<=N<1000
1<=ai<=1000

Sample Input 0

6
5 4 4 2 2 8
Sample Output 0

6
4
2
1
Sample Input 1

8
1 2 3 4 3 3 2 1
Sample Output 1

8
6
4
1

Explanation

Sample Case 0 :

sticks-length length-of-cut sticks-cut
5 4 4 2 2 8 2 6
3 2 2 _ _ 6 2 4
1 _ _ _ _ 4 1 2
_ _ _ _ _ 3 3 1
_ _ _ _ _ _ DONE DONE
Sample Case 1:

sticks-length length-of-cut sticks-cut
1 2 3 4 3 3 2 1 1 8
_ 1 2 3 2 2 1 _ 1 6
_ _ 1 2 1 1 _ _ 1 4
_ _ _ 1 _ _ _ _ 1 1
_ _ _ _ _ _ _ _ DONE DONE

For Learning More: https://coderinme.com/

solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int N;
    cin >> N;
    int stick[N];
    for (int i = 0; i < N; i++) {
        cin >> stick[i];
    }

    sort(stick, stick+N);  //arrange array in increasing order

    int remain = N;
    cout << remain << endl;

    int shortest = stick[0];
    for (int i = 1; i < N; i++) {
        if (stick[i] != shortest) {
            shortest = stick[i];
            remain = N - i;
            cout << remain << endl;
        }
    }

    return 0;
}
N = input()
num = map(int, raw_input().split())
val = [0] * 1001
for i in num:
    val[i] += 1
counter = 0
val = val[::-1]
ans = []
for i in val:
    if i > 0:
        counter += i
        ans.append(counter)
ans = ans[::-1]
for i in ans:
    print i
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Solution {
	static BufferedReader in = new BufferedReader(new InputStreamReader(
			System.in));
	static StringBuilder out = new StringBuilder();

	public static void main(String[] args) throws IOException {
		int[] stickAmts = new int[1001];
		int numSticks = Integer.parseInt(in.readLine());
		String line = in.readLine();
		String[] data = line.split("\\s+");
		for(int i = 0; i < numSticks; i ++)
		{
			stickAmts[Integer.parseInt(data[i])]++;
		}
		for(int i = 1; i <= 1000; i ++)
		{
			if(stickAmts[i] != 0)
			{
				System.out.println(numSticks);
				numSticks -= stickAmts[i];
			}
		}
	}
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.