Given n number of buckets and each bucket is numbered from 1 to n and flowers in it are equal to triangular numbers. You have to choose the bucket which is left with minimum flower after picking ‘p’ flowers from it.
First bucket contains only 1 flower, second bucket contains 3, third bucket contains 6 and so on following a pattern of n(n+1)/2.
Examples :
Input : p = 4 Output : bucket 3 Explanation : Buckets with flowers : 1 3 6 10 .... So, bucket 3 is left with only two flowers after selecting p flowers from it which is minimum. Input : p = 10 Output : bucket 4 Explanation : Bucket with flowers : 1 3 6 10 15 ... So, selecting 10 flowers from 4th bucket leave it with 0 flowers.
Approach :
Observing the input/output of different cases, bucket number can be calculated using formula :
n = ceil( (sqrt(8*p+1)-1)/2 ) ;
How does it work?
We need smallest n such than n*(n+1)/2 >= p
So we need to find roots of equation n2 + n – 2*p >= 0.
By applying the formula discussed here, we get n = ceil( (sqrt(8*p+1)-1)/2 )
C++
// CPP code to find the bucket to choose // for picking flowers out of it#include<bits/stdc++.h>using namespace std;int findBucketNo(int p){ return ceil( ( sqrt( 8*p + 1 ) -1 ) / 2 ) ;}// Driver codeint main(){ int p = 10 ; cout << findBucketNo(p); return 0;} |
Java
//Java code to find the bucket to choose // for picking flowers out of itimport java.lang.System.*;class GFG { static int findBucketNo(int p) { return (int)Math.ceil(( Math.sqrt( 8*p + 1 ) -1 ) / 2 ) ; } // Driver code public static void main(String[] args) { int p = 10 ; System.out.println(findBucketNo(p)); }}// This code is contributed by// Smitha Dinesh Semwal |
Python 3
# Python 3 code to find the bucket # to choose for picking flowers# out of itimport mathdef findBucketNo(p): return math.ceil( ( math.sqrt( 8*p + 1 ) -1 ) / 2 ) # Driver codep = 10print(findBucketNo(p))# This code is contributed by# Smitha Dinesh Semwal |
C#
// C# code to find the bucket to choose // for picking flowers out of itusing System;class GFG { static int findBucketNo(int p) { return (int)Math.Ceiling(( Math.Sqrt( 8*p + 1 ) -1 ) / 2 ); } // Driver code static public void Main () { int p = 10 ; Console.WriteLine(findBucketNo(p)); }}// This code is contributed by Ajit. |
PHP
<?php// PHP code to find the bucket // to choose for picking // flowers out of itfunction findBucketNo($p){ return ceil( ( sqrt( 8 * $p + 1 ) -1 ) / 2 ) ;}// Driver code$p = 10 ; echo(findBucketNo($p));// This code is contributed by Ajit.?> |
Javascript
<script>// javascript code to find the bucket to choose // for picking flowers out of itfunction findBucketNo( p){ return Math.ceil( ( Math.sqrt( 8 * p + 1 ) -1 ) / 2 ) ;}// Driver codelet p = 10 ; document.write(findBucketNo(p)); // This code is contributed by gauravrajput1 </script> |
4
Time Complexity : O(logn)
Auxiliary Space: O(1) as it is using constant space for variables
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
