The smallest triangular number greater than p

We will discuss triangle numbers and how to find the smallest number of triangles that is only greater than the given number "num". Let’s first discuss what trigonometric numbers are, and then find the smallest trigonometric number larger than “num”

We will see two different approaches to the same problem. In the first method we will run a simple loop to generate the output, while in the second method we will first generate a general formula for calculating the required number and then directly apply that formula to get the minimum Triangle number. p>

Problem Statement

We must find the smallest number of triangles that is only larger than "num".

We have multiple boxes containing balls. The number of balls the box contains is a different triangular number for all boxes. The boxes are numbered from 1 to n. We have to find out which box will contain the minimum number of balls after removing "num" balls from the box.

Let us understand this through an example

Input number was: num = 5

We have to find out which box has the least number of balls after taking out 5 balls

Output:3rd box will contain a minimum of balls after removing 4 balls.

Solution for this example -

Boxes with number of balls: {1 3 6 10 ....}
Box 3 will contain only 1 ball after removing 4 balls from it.

What are trigonometric numbers?

Triangle numbers are numbers that can be represented in the form of an equilateral triangle grid. The number of points in a row is always equal to the row number, i.e. the first row will contain 1 point, the second row will contain 2 points, and so on. Several triangle numbers are: 1, 3, 6, 10, 15…. Now let us derive the formula for the nth triangular number -

We know that the nth row of the triangle number contains n points, so the triangle number can be expressed as the sum of the points in each row. We also know that the nth trigonometric number has n rows, so the nth trigonometric number can be given by the sum of the first n natural numbers.

Method 1: (direct method)

In this method, we will run a loop and calculate the difference between the given number and the nth trigonometric number, when we get the difference >= 0, we will get the desired box number, So we're going to truncate the loop.

For triangular numbers, we will continue to add n to the existing (n-1)th triangular number to calculate the value of the next triangular number.

algorithm

• Step 1 - Initialize the variable triangular_number to 0.

• Step 2 - Run the for loop and keep adding n for each iteration.

• Step 3 - Continue to calculate the difference between the triangle number and the given number "num".

• Step 4 - When we get the difference >=0, we will print n as the desired box number.

Example

The implementation of this method in C is as follows -

#include <iostream>
using namespace std;
int main(){
   int num = 1234;
   int triangular_number = 0;
   for (int n=1; triangular_number<=num; n++){
      triangular_number = triangular_number + n;
      if((triangular_number-num)>=0){
         cout<<"The smallest triangular number larger than "<<num<<" is "<<n;
         return 0;
      }
   }
}

Output

The smallest triangular number larger than 1234 is 50

Method 2: Formula-based method

In this method, we first generate a general formula for calculating the required number and then directly apply the formula to obtain the smallest number of triangles that is only larger than the given number.

The triangle number of the nth box number is given by the following formula -

Triangular number = (n*(n+1))/2

Get the smallest box number "n" such that the number of triangles >= num.

i.e. (n*(n+1))/2 >= num

This means we have to solve -

n<sup>2</sup> + n – 2*num >= 0

Using this equation, we get

n = ceil( (sqrt(8*num+1)-1)/2 )

Example

The code for this method is given below -

#include<bits/stdc++.h>
using namespace std;
int boxnum(int num){
   return ceil( ( sqrt( 8*num + 1 ) -1 ) / 2 ) ;
}
int main(){
   int num = 1234 ;
   cout << "The smallest triangular number larger than "<<num<<" is "<<boxnum(num);
   return 0;
}

Output

The smallest triangular number larger than 1234 is 50

Time complexity of this method - O(logn)

Space Complexity - O(1) since we only use constant extra space.

In this article, we discussed two different methods to find the smallest number of triangles that is only larger than a given number "num". The first method simply calculates the trigonometric numbers by running a loop and adding n for each iteration. We also calculated the difference between the given number and the trigonometric number. In the second approach, we generate a mathematical formula to calculate our desired output.

The above is the detailed content of The smallest triangular number greater than p. For more information, please follow other related articles on the PHP Chinese website!