Given a positive integer N, the task is to find the Nth item given out when there are infinite items of the infinite number of types such that the items are given out in the following fashion:
- Day 1: 1 item of Type-I are given out.
- Day 2: 2 items of the Type-II and 1 item of Type-I are given out.
- Day 3: 3 items of the Type-III, 2 items of the Type-II, and 1 item of Type-I are given out.
- Day 4: 4 items of the Type-IV, 3 items of the Type-III, 2 items of the Type-II, and 1 item of Type-I are given out.
- and so on…
Examples:
Input: N = 10
Output: 1
Explanation:
Following are the orders of the items given out:
- Day 1: 1 item of Type-I are given out. The sequence is {1}.
- Day 2: 2 items of the Type-II and 1 item of Type-I are given out. The sequence is {1, 2, 2, 1}.
- Day 3: 3 items of the Type-III, 2 items of the Type-II, and 1 item of Type-I are given out. The sequence is {1, 2, 2, 1, 3, 3, 3, 2, 2, 1}.
From the above order of items removed, the Nth(= 10th) item given out is 1. Therefore, print 1.
Input: N = 399
Output: 11
Approach: The simplest approach to solve the given problem is to keep the track of the number of days and the count of the number of items given on each day by following the given order and print that item which is given out at the Nth turn.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the type of the// item given out according to the// given rulesint itemType(int n){ // Stores the count of item given // out at each step int count = 0; // Iterate over the days from 1 for (int day = 1;; day++) { // Iterate over type of item // on that day for (int type = day; type > 0; type--) { count += type; // Count of items given out // should exceed n if (count >= n) return type; } }}// Driver Codeint main(){ int N = 10; cout << itemType(N); return 0;} |
Java
// Java Program for the above approachimport java.io.*;class GFG { // Function to find the type of the// item given out according to the// given rulesstatic int itemType(int n){ // Stores the count of item given // out at each step int count = 0; // Iterate over the days from 1 for (int day = 1;; day++) { // Iterate over type of item // on that day for (int type = day; type > 0; type--) { count += type; // Count of items given out // should exceed n if (count >= n) return type; } }}// Driver Code public static void main (String[] args) { int N = 10; System.out.println( itemType(N)); }}// This code is contributed by Potta Lokesh |
Python3
# Python3 program for the above approach# Function to find the type of the# item given out according to the# given rulesdef itemType(n): # Stores the count of item given # out at each step count = 0 # Iterate over the days from 1 day = 1 while(True): # Iterate over type of item # on that day for type in range(day, 0, -1): count += type # Count of items given out # should exceed n if (count >= n): return type# Driver CodeN = 10print(itemType(N))# This code is contributed by ShubhamSingh10 |
C#
//C# code for the above approachusing System;public class GFG{ // Function to find the type of the // item given out according to the // given rules static int itemType(int n) { // Stores the count of item given // out at each step int count = 0; // Iterate over the days from 1 for (int day = 1;; day++) { // Iterate over type of item // on that day for (int type = day; type > 0; type--) { count += type; // Count of items given out // should exceed n if (count >= n) return type; } } } // Driver Code static public void Main () { int N = 10; Console.WriteLine( itemType(N)); }}// This code is contributed by shubhamsingh10. |
Javascript
// Javascript program for the above approach// Function to find the type of the// item given out according to the// given rulesfunction itemType(n) { // Stores the count of item given // out at each step let count = 0; // Iterate over the days from 1 for (let day = 1; ; day++) { // Iterate over type of item // on that day for (let type = day; type > 0; type--) { count += type; // Count of items given out // should exceed n if (count >= n) return type; } }}// Driver Codelet N = 10;document.write(itemType(N));// This code is contributed by _saurabh_jaiswal. |
Output:
1
Time Complexity: O(N)
Auxiliary Space: O(1), since no extra space has been taken.
Efficient Approach: The above approach can also be optimized by using the fact that on a given particular day D the number of items given out is the sum of numbers from 1 to D and the sum of numbers from day 1 to that day should be less than equal to N. Follow the steps below to solve the problem:
- Initialize the variables, say count as 0 to store the number of items given and day to store the number of items for that day.
- Iterate a loop until the value of (count + day*(day + 1))/2 is less than N and perform the following steps:
- Add the value of day*(day + 1)/2 to the variable count.
- Increase the value of the day by 1.
- Iterate over a range [day, 0] using the variable type and performing the following tasks:
- Add the value of type to the variable count.
- If the value of count is greater than equal to N, then print the value of type as the resultant answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the type of the// item given out according to the// given rulesint itemType(int n){ // Stores the count of item given // out at each step int count = 0; int day = 1; // Iterate to find the Nth day // present is given out while (count + day * (day + 1) / 2 < n) { // Find the number of presents // given on day is day*(day+1)/2 count += day * (day + 1) / 2; day++; } for (int type = day; type > 0; type--) { // Iterate over the type count += type; // Return the resultant type if (count >= n) { return type; } }}// Driver Codeint main(){ int N = 10; cout << itemType(N); return 0;} |
Java
// Java program for the above approachimport java.util.*; class GFG { // Function to find the type of the// item given out according to the// given rulesstatic int itemType(int n){ // Stores the count of item given // out at each step int count = 0; int day = 1; // Iterate to find the Nth day // present is given out while (count + day * (day + 1) / 2 < n) { // Find the number of presents // given on day is day*(day+1)/2 count += day * (day + 1) / 2; day++; } for (int type = day; type > 0; type--) { // Iterate over the type count += type; // Return the resultant type if (count >= n) { return type; } } return 0;}// Driver Codepublic static void main(String[] args) { int N = 10; System.out.println( itemType(N));}}// This code is contributed by shivanisinghss2110 |
Python3
# Python 3 program for the above approach# Function to find the type of the# item given out according to the# given rulesdef itemType(n): # Stores the count of item given # out at each step count = 0 day = 1 # Iterate to find the Nth day # present is given out while (count + day * (day + 1) // 2 < n): # Find the number of presents # given on day is day*(day+1)/2 count += day * (day + 1) // 2; day += 1 type = day while(type > 0): # Iterate over the type count += type # Return the resultant type if (count >= n): return type type -= 1# Driver Codeif __name__ == '__main__': N = 10 print(itemType(N)) # This code is contributed by bgaangwar59. |
C#
// C# program for the above approachusing System; class GFG { // Function to find the type of the// item given out according to the// given rulesstatic int itemType(int n){ // Stores the count of item given // out at each step int count = 0; int day = 1; // Iterate to find the Nth day // present is given out while (count + day * (day + 1) / 2 < n) { // Find the number of presents // given on day is day*(day+1)/2 count += day * (day + 1) / 2; day++; } for (int type = day; type > 0; type--) { // Iterate over the type count += type; // Return the resultant type if (count >= n) { return type; } } return 0;}// Driver Codepublic static void Main(String[] args) { int N = 10; Console.Write ( itemType(N));}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach// Function to find the type of the// item given out according to the// given rulesfunction itemType(n){ // Stores the count of item given // out at each step let count = 0; let day = 1; // Iterate to find the Nth day // present is given out while (count + day * (day + 1) / 2 < n) { // Find the number of presents // given on day is day*(day+1)/2 count += day * (day + 1) / 2; day++; } for(let type = day; type > 0; type--) { // Iterate over the type count += type; // Return the resultant type if (count >= n) { return type; } }}// Driver codelet N = 10;document.write(itemType(N));// This code is contributed by sanjoy_62</script> |
Output:
1
Time Complexity: O(sqrt(N))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
