HackerRank Bonetrousle Problem Solution
In this post, we will solve HackerRank Bonetrousle Problem Solution.
Here’s a humerus joke:
Why did Papyrus the skeleton go to the store by himself? Because he had no body to go with him!
Did you like it? Don’t worry, I’ve got a ton more. A skele-ton.
Once upon a time, Papyrus the skeleton went to buy some pasta from the store. The store’s inventory is bare-bones and they only sell one thing – boxes of uncooked spaghetti! The store always stocks exactly k boxes of pasta, and each box is numbered sequentially from 1 to k. This box number also corresponds to the number of sticks of spaghetti in the box. meaning the first box contains 1 stick, the second box contains 2 sticks, the third box contains 3 sticks…. and the kth box contains k sticks. Because they only stock one box of each kind, the store has a tendon-cy to sell out of spaghetti.
During each trip to the store, Papyrus likes to buy exactly n sticks of spaghetti by purchasing exactly b boxes (no more, no less). Not sure which boxes to purchase, Papyrus calls Sherlock Bones for help but he’s also stumped! Do you have the guts to solve this puzzle?
Given the values of n. k, and b fort trips to the store, determine which boxes Papyrus must purchase during each trip. For each trip, print a single line of b distinct space-separated integers denoting the box number for each box of spaghetti Papyrus purchases (recall that the store only has one box of each kind). If it’s not possible to buy n sticks of spaghetti by purchasing b boxes, print – 1 instead.
For example, Papyrus wants to purchase n = 14 sticks of spaghetti in b = 3 boxes and the store has k = 8 different box sizes. He can buy boxes of sizes [8, 4, 2], [7, 5, 2], [7, 6, 1] and other combinations. Any of the combinations will work.
Function Description
Complete the bonetrousle function in the editor below. It should return an array of integers.
bonetrousle has the following parameter(s):
- n: the integer number of sticks to buy
- k: the integer number of box sizes the store carries
- b: the integer number of boxes to buy
Input Format
The first line contains a single integer t, the number of trips to the store.
Each of the next t lines contains three space-separated integers n, k and b, the number of sticks to buy, the number of boxes for sale and the number of boxes to buy on this trip to the store.
Output Format
For each trip to the store:
- If there is no solution, print
-1on a new line. - If there is a solution, print a single line of b distinct space-separated integers where each integer denotes the numbers of noodles in each box that Papyrus must purchase.
If there are multiple possible solutions, you can print any one of them. Do not print any leading or trailing spaces or extra newlines.
Sample Input
4
12 8 3
10 3 3
9 10 2
9 10 2
Sample Output
2 3 7
-1
5 4
1 8
Bonetrousle C Solution
#include<stdio.h>
#include<stdlib.h>
unsigned long long int add( unsigned long long int a, unsigned long long int b);
unsigned long long int check( unsigned long long int number, unsigned long long int k, unsigned long long int max);
int main() {
int test;
scanf("%d", &test);
while( test--) {
unsigned long long int number,k,max;
scanf("%lld%lld%lld", &number,&max,&k);
unsigned long long int d = check(number,k,max);
//printf("d = %lld\n\n", d);
if(~d) {
unsigned long long int x = (number-d)/k;
unsigned long long int i1 = x+1,i2 = x+1,j1 = i1+k-1,j2 = i1+k-1;
unsigned long long int sum = add(i1,j1);
//printf("sum = %d", sum);
unsigned long long int mod = number-sum;
j2++;
i2 = j2- mod+1;
j1 = i2-2;
unsigned long long int cnt = 0;
unsigned long long int array[k];
for( unsigned long long int i = i1; i <= j1; i++) {array[cnt] = i;cnt++;}
for( unsigned long long int i = i2; i <= j2; i++) {array[cnt] = i;cnt++;}
for( unsigned long long int i = 0; i < cnt-1; i++) printf("%lld ", array[i]);
printf("%lld", array[cnt-1]);
}
else printf("-1");
printf("\n");
}
return 0;}
unsigned long long int check( unsigned long long int number, unsigned long long int k, unsigned long long int max){
unsigned long long int sum1 = 0,sum2 = 0;
// printf("max = %d", max)
for( unsigned long long int i = 1; i <= k; i++) {sum1+=i; sum2+= (max-i+1);}
//printf("sum1 = %lld sum2 = %lld\n\n", sum1,sum2);
if( sum1 > number || sum2 < number) return -1;
return sum1;
}
unsigned long long int add( unsigned long long int a, unsigned long long int b){
unsigned long long int sum = 0;
for( unsigned long long int i = a; i <=b; i++) sum+=i;
return sum;
}Bonetrousle C++ Solution
#include <iostream>
#include <cstdint>
using namespace std;
const int B = 1e5;
uint64_t n, k, a[B + 2];
int b;
int main() {
ios_base::sync_with_stdio(0);
int t;
cin >> t;
for (int tt = 0; tt < t; ++tt) {
cin >> n >> k >> b;
uint64_t total = 0;
for (int i = 1; i <= b; ++i) {
a[i] = i;
total += i;
}
if (total > n) {
cout << -1 << endl;
continue;
}
a[b + 1] = k + 1;
bool solved = false;
for (int i = b; i >= 1; --i) {
uint64_t temp = a[i];
a[i] = min(a[i + 1] - 1, a[i] + n - total);
total += (a[i] - temp);
if (total == n) {
solved = true;
break;
}
}
if (solved) {
for (int i = 1; i <= b - 1; ++i)
cout << a[i] << " ";
cout << a[b] << endl;
} else {
cout << -1 << endl;
}
}
}Bonetrousle C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
class Solution {
static void Main(string[] args)
{
int T = int.Parse(Console.ReadLine());
for(int i = 0; i < T; i++)
{
string[] parts = Console.ReadLine().Split(' ');
long N = long.Parse(parts[0]);
long K = long.Parse(parts[1]);
int B = int.Parse(parts[2]);
Solve(N, K, B);
}
}
static void Solve(long N, long K, int B)
{
long min = ((long)B) * (((long)B) + 1) / 2;
if (N < min)
{
Console.WriteLine(-1);
}
else
{
long[] result = new long[B];
long total = min;
long nextAvailable = K;
for(int i = B;i > 0; i--)
{
long shift = Math.Min(N - total, nextAvailable - i);
result[i - 1] = i + shift;
nextAvailable--;
total += shift;
}
if (total == N)
{
Console.WriteLine(string.Join(" ", result));
}
else
{
Console.WriteLine(-1);
}
}
}
}Bonetrousle Java Solution
import java.io.*;
import java.util.*;
import java.math.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner in = new Scanner(System.in);
int T = in.nextInt();
long[] result = new long[100000];
for (int t = 0; t < T; t++) {
long n = in.nextLong();
long k = in.nextLong();
int b = in.nextInt();
long minSum = (long) (1 + b) * b / 2;
BigInteger maxSum = BigInteger.valueOf(k + k - (b - 1)).multiply(BigInteger.valueOf(b)).divide(BigInteger.valueOf(2));
if (n < minSum || BigInteger.valueOf(n).compareTo(maxSum) > 0) {
System.out.println(-1);
} else {
long div = (n - minSum) / b;
int mod = (int) ((n - minSum) % b);
for (int i = 0; i < b; i++) {
result[i] = i + 1 + div;
}
if (mod != 0) {
long next = result[b - 1] + 1;
result[b - mod] = next;
}
StringBuilder out = new StringBuilder();
for (int i = 0; i < b; i++) {
if (i > 0) {
out.append(" ");
}
out.append(result[i]);
}
System.out.println(out.toString());
}
}
}
}Bonetrousle JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.split('\n');
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the 'bonetrousle' function below.
*
* The function is expected to return a LONG_INTEGER_ARRAY.
* The function accepts following parameters:
* 1. LONG_INTEGER n
* 2. LONG_INTEGER k
* 3. INTEGER b
*/
// function bonetrousle(n, k, b) {
// // Write your code here
// const max = (k * (k + 1) - (k - b) * (k - b + 1))/2
// const min = (b + 1) * b / 2;
// if( max < n || min > n) return [-1]
// const diff = max - n;
// const solution = new Array(b)
// for (let i = k; i > k - b; i --) {
// solution[k - i] = i
// }
// const maxSub = solution[b - 1] - 1
// if ( maxSub > 0 ) {
// const subCount = parseInt(diff / maxSub);
// const subRest = diff - maxSub * subCount
// for (let i = 0; i < subCount; i ++) {
// solution[b - i - 1] -= maxSub
// // console.log('for in', b - i - 1, solution[b - i - 1])
// }
// if(subRest !== 0) {
// if (b - 1 - subCount < 0) return [-1]
// solution[b - 1 - subCount] -= subRest
// }
// }
// return solution
// }
function bonetrousle(n, k, b) {
const max = (k * (k + 1n) - (k - b) * (k - b + 1n)) / 2n;
const min = (b + 1n) * b / 2n;
if (max < n || min > n) return [-1n];
const diff = max - BigInt(n);
const solution = new Array(b);
for (let i = k; i > k - b; i--) {
solution[k - i] = BigInt(i);
}
const maxSub = BigInt(solution[BigInt(b) - 1n]) - 1n;
if (maxSub > 0n) {
const subCount = diff / maxSub;
const subRest = diff - maxSub * subCount;
for (let i = 0; i < subCount; i++) {
solution[BigInt(b) - BigInt(i) - 1n] -= maxSub;
}
if (subRest !== 0n) {
if (BigInt(b) - 1n - subCount < 0n) return [-1n];
solution[BigInt(b) - 1n - BigInt(subCount)] -= subRest;
}
}
return solution;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const t = parseInt(readLine().trim(), 10);
for (let tItr = 0; tItr < t; tItr++) {
const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');
const n = BigInt(firstMultipleInput[0]);
const k = BigInt(firstMultipleInput[1]);
const b = BigInt(firstMultipleInput[2]);
const result = bonetrousle(n, k, b);
ws.write(result.join(' ') + '\n');
}
ws.end();
}Bonetrousle Python Solution
t = int(input())
for tc in range(t):
n, k, b = map(int, input().split())
taken = list(range(1, b+1))
total = sum(taken)
max_available = k
for i in reversed(range(b)):
remaining = n - total
if remaining <= 0:
break
new_val = min(taken[i] + remaining, max_available)
max_available = new_val - 1
total += new_val - taken[i]
taken[i] = new_val
if total != n:
print(-1)
else:
print(' '.join(map(str, taken)))
