Find the XOR of smallest and largest triangular number in a given range
Given a range, find the XOR of the smallest and largest triangular numbers within that range.
A triangular number is a number that can be represented as the sum of consecutive positive integers starting from 1. In other words, a triangular number is the sum of the first n natural numbers, where n is a positive integer. The formula for the nth triangular number is: Tn = 1 + 2 + 3 + … + n = n(n+1)/2
For example, the first few triangular numbers are:
T1 = 1
T2 = 1 + 2 = 3
T3 = 1 + 2 + 3 = 6
T4 = 1 + 2 + 3 + 4 = 10
Examples:
Input: Range [60, 195]
Output: 252
Explanation: Smallest triangular number in the given range is 66, and the largest triangular number in the given range is 190. The XOR of 66 and 190 is 252.Input: Range [100, 280]
Output: 381
Explanation: Smallest triangular number in the given range is 105, and the largest triangular number in the given range is 276. The XOR of 105 and 276 is 381.
Approach: This can be solved with the following idea:
The idea behind this approach is to first define a function to find the nth triangular number using the formula n*(n+1)/2. Then, we define two functions to find the smallest and largest triangular numbers within a given range. To find the smallest triangular number within the range, we simply iterate through the triangular numbers until we find the first triangular number that is greater than or equal to the lower bound, and return that triangular number if it is also less than or equal to the upper bound. If there is no triangular number within the range, we return -1. To find the largest triangular number within the range, we again iterate through the triangular numbers, but this time we return the previous triangular number when we find the first triangular number that is greater than the upper bound. This is because the previous triangular number is the largest triangular number within the range. If there is no triangular number within the range, we return 0.
Steps of the above approach:
- Define a function findTriangularNumber(n) that takes an integer n and returns the nth triangular number. The formula to find the nth triangular number is n*(n+1)/2.
- Define a function findSmallestTriangularNumberInRange(lower_bound, upper_bound) that takes the lower and upper bounds of the range as input and returns the smallest triangular number within that range.
- This can be done by iterating through the triangular numbers until you find the first triangular number that is greater than or equal to the lower bound, and returning that triangular number if it is also less than or equal to the upper bound. If there is no triangular number within the range, return -1.
- Define a function findLargestTriangularNumberInRange(lower_bound, upper_bound) that takes the lower and upper bounds of the range as input and returns the largest triangular number within that range.
- This can be done by iterating through the triangular numbers until you find the first triangular number that is greater than the upper bound and returning the previous triangular number, which is the largest triangular number within the range. If there is no triangular number within the range, return 0.
- Finally, in the main() function, we call these two functions with the given range and check if either of them returns -1 or 0. If not, we XOR the smallest and largest triangular numbers and print the result.
Below is the implementation of the above approach:
C++
// C++ code of the above approach: #include <bits/stdc++.h> using namespace std; // Function to find triangular number int findTriangularNumber( int n) { return n * (n + 1) / 2; } // Function to find smallest triangular // number above the smallest range int findSmallestTriangularNumberInRange( int lower_bound, int upper_bound) { for ( int n = 1;; n++) { int triangular_number = findTriangularNumber(n); if (triangular_number >= lower_bound && triangular_number <= upper_bound) { return triangular_number; } else if (triangular_number > upper_bound) { return -1; } } } // Function to find largest triangular // number below the range int findLargestTriangularNumberInRange( int lower_bound, int upper_bound) { int largest_triangular_number = 0; for ( int n = 1;; n++) { int triangular_number = findTriangularNumber(n); if (triangular_number > upper_bound) { return largest_triangular_number; } else if (triangular_number >= lower_bound) { largest_triangular_number = triangular_number; } } } // Driver code int main() { int lower_bound = 100, upper_bound = 280; // Function call int smallest_triangular_number = findSmallestTriangularNumberInRange(lower_bound, upper_bound); int largest_triangular_number = findLargestTriangularNumberInRange(lower_bound, upper_bound); if (smallest_triangular_number == -1 || largest_triangular_number == 0) { cout << "-1" << endl; } else { int result = smallest_triangular_number ^ largest_triangular_number; cout << result << endl; } return 0; } |
Java
import java.util.*; class GFG { // Function to find triangular number static int findTriangularNumber( int n) { return n * (n + 1 ) / 2 ; } // Function to find smallest triangular number above the smallest range static int findSmallestTriangularNumberInRange( int lowerBound, int upperBound) { for ( int n = 1 ;; n++) { int triangularNumber = findTriangularNumber(n); if (triangularNumber >= lowerBound && triangularNumber <= upperBound) { return triangularNumber; } else if (triangularNumber > upperBound) { return - 1 ; } } } // Function to find largest triangular number below the range static int findLargestTriangularNumberInRange( int lowerBound, int upperBound) { int largestTriangularNumber = 0 ; for ( int n = 1 ;; n++) { int triangularNumber = findTriangularNumber(n); if (triangularNumber > upperBound) { return largestTriangularNumber; } else if (triangularNumber >= lowerBound) { largestTriangularNumber = triangularNumber; } } } // Driver code public static void main(String[] args) { int lowerBound = 100 , upperBound = 280 ; // Function call int smallestTriangularNumber = findSmallestTriangularNumberInRange(lowerBound, upperBound); int largestTriangularNumber = findLargestTriangularNumberInRange(lowerBound, upperBound); if (smallestTriangularNumber == - 1 || largestTriangularNumber == 0 ) { System.out.println( "-1" ); } else { int result = smallestTriangularNumber ^ largestTriangularNumber; System.out.println(result); } } } |
Python3
# python code of the above approach: # Function to find triangular number def find_triangular_number(n): return n * (n + 1 ) / / 2 # Function to find smallest triangular number above the smallest range def find_smallest_triangular_number_in_range(lower_bound, upper_bound): n = 1 while True : triangular_number = find_triangular_number(n) if triangular_number > = lower_bound and triangular_number < = upper_bound: return triangular_number elif triangular_number > upper_bound: return - 1 n + = 1 # Function to find largest triangular number below the range def find_largest_triangular_number_in_range(lower_bound, upper_bound): largest_triangular_number = 0 n = 1 while True : triangular_number = find_triangular_number(n) if triangular_number > upper_bound: return largest_triangular_number elif triangular_number > = lower_bound: largest_triangular_number = triangular_number n + = 1 # Driver code def main(): lower_bound = 100 upper_bound = 280 # Function calls smallest_triangular_number = find_smallest_triangular_number_in_range(lower_bound, upper_bound) largest_triangular_number = find_largest_triangular_number_in_range(lower_bound, upper_bound) if smallest_triangular_number = = - 1 or largest_triangular_number = = 0 : print ( "-1" ) else : result = smallest_triangular_number ^ largest_triangular_number print (result) main() |
C#
using System; public class Program { // Function to find triangular number public static int FindTriangularNumber( int n) { // Triangular number formula: n*(n+1)/2 return n * (n + 1) / 2; } // Function to find smallest triangular number above the smallest range public static int FindSmallestTriangularNumberInRange( int lower_bound, int upper_bound) { for ( int n = 1; ; n++) { int triangular_number = FindTriangularNumber(n); if (triangular_number >= lower_bound && triangular_number <= upper_bound) { // Found the smallest triangular number within the range return triangular_number; } else if (triangular_number > upper_bound) { // No triangular number found within the range return -1; } } } // Function to find largest triangular number below the range public static int FindLargestTriangularNumberInRange( int lower_bound, int upper_bound) { int largest_triangular_number = 0; for ( int n = 1; ; n++) { int triangular_number = FindTriangularNumber(n); if (triangular_number > upper_bound) { // Found the largest triangular number below the range return largest_triangular_number; } else if (triangular_number >= lower_bound) { // Update the largest triangular number within the range largest_triangular_number = triangular_number; } } } // Driver code public static void Main() { int lower_bound = 100; int upper_bound = 280; // Function calls int smallest_triangular_number = FindSmallestTriangularNumberInRange(lower_bound, upper_bound); int largest_triangular_number = FindLargestTriangularNumberInRange(lower_bound, upper_bound); if (smallest_triangular_number == -1 || largest_triangular_number == 0) { Console.WriteLine( "-1" ); // No valid triangular numbers within the range } else { int result = smallest_triangular_number ^ largest_triangular_number; Console.WriteLine(result); } } } |
Javascript
function findTriangularNumber(n) { return n * (n + 1) / 2; } // Function to find smallest triangular number above // the smallest range function findSmallestTriangularNumberInRange(lower_bound, upper_bound) { for (let n = 1;; n++) { const triangular_number = findTriangularNumber(n); if (triangular_number >= lower_bound && triangular_number <= upper_bound) { return triangular_number; } else if (triangular_number > upper_bound) { return -1; } } } // Function to find largest triangular number below the range function findLargestTriangularNumberInRange(lower_bound, upper_bound) { let largest_triangular_number = 0; for (let n = 1;; n++) { const triangular_number = findTriangularNumber(n); if (triangular_number > upper_bound) { return largest_triangular_number; } else if (triangular_number >= lower_bound) { largest_triangular_number = triangular_number; } } } // Driver code function main() { const lower_bound = 100; const upper_bound = 280; // Function calls const smallest_triangular_number = findSmallestTriangularNumberInRange(lower_bound, upper_bound); const largest_triangular_number = findLargestTriangularNumberInRange(lower_bound, upper_bound); if (smallest_triangular_number === -1 || largest_triangular_number === 0) { console.log( "-1" ); } else { const result = smallest_triangular_number ^ largest_triangular_number; console.log(result); } } main(); |
381
Time Complexity: O(sqrt(n))
Auxiliary Space: O(1)
Contact Us