We are given a number N. We need to check if the given number N can be represented as sum of two Great numbers. If yes then print those two great numbers else print no. Great numbers are those which are represented in the form : ((b)*(b+1)*(2*b+1))/6 where b is a natural number. Examples:
Input : N = 35
Output : 5 and 30
Input : 105
Output : 14 and 91
Input : 99
Output : No the given number is not
a sum of two great numbers
As we know ((b)*(b+1)*(2*b+1))/6 where b is a natural number represents the sum of square of first b natural numbers. For example if b = 3 then 1+4+9 = 14. So to check if the input number n can be represented as sum of two great numbers then we will first compute all the great numbers less than n in an array. Then we will use two pointer approach to find the pair than can sum up to the given number n. To compute the array of all the great numbers we will iterate over i=0 to i
C++
#include <iostream>#include <vector>using namespace std;void countPairs(int arr[], int tar, int size) { // Here the array is already sorted // so we can find the pair in // O(n) time int lo = 0, hi = size - 1; bool check = false; while (lo < hi) { if (arr[lo] + arr[hi] == tar) { check = true; // if sum of both pointers is equal to target cout << arr[lo] << " and " << arr[hi] << endl; hi--; } else if (arr[lo] + arr[hi] < tar) { // if sum is less than target then increment // the lower index to increase the sum lo++; } else { // if sum is greater than target then // decrement the higher index to decrease // the sum hi--; } } // if no single pair was found then check // will be false if(!check) cout << "No the given number is not a sum of two great numbers" << endl; }// Find the two great numbers in O(n) Time and // O(n) auxiliary space void greatNumberComputation(int n) { // To precompute all the great numbers // less than N vector<int> arr; // Traverse from 0 to n and add square of // current i with the sum of previous // index of array int temp = 0; for (int i = 0; temp < n; i++) { temp += i * i; arr.push_back(temp); } int* a = new int[arr.size()]; for (int i = 0; i < arr.size(); i++) a[i] = arr[i]; countPairs(a, n, arr.size()); delete[] a;} // Driver code int main() { int n = 105; greatNumberComputation(n); return 0;}// This code is contributed by Utkarsh. |
Java
import java.util.*;public class Gfg { static void countPairs(int arr[], int tar, int size) { // Here the array is already sorted // so we can find the pair in // O(n) time int lo = 0, hi = size - 1; boolean check = false; while (lo < hi) { if (arr[lo] + arr[hi] == tar) { check = true; // if sum of both pointers is equal to target System.out.println(arr[lo] + " and " + arr[hi]); hi--; } else if (arr[lo] + arr[hi] < tar) { // if sum is less than target then increment // the lower index to increase the sum lo++; } else { // if sum is greater than target then // decrement the higher index to decrease // the sum hi--; } } // if no single pair was found then check // will be false if(!check) System.out.println("No the given number is not a sum of two great numbers"); } // Find the two great numbers in O(n) Time and // O(n) auxiliary space static void greatNumberComputation(int n) { // To precompute all the great numbers // less than N ArrayList<Integer> arr = new ArrayList<>(); // Traverse from 0 to n and add square of // current i with the sum of previous // index of array int temp = 0; for (int i = 0; temp < n; i++) { temp += i * i; arr.add(temp); } int[] a = new int[arr.size()]; for (int i = 0; i < arr.size(); i++) a[i] = arr.get(i); countPairs(a, n, arr.size()); } // Driver code public static void main(String[] args) { int n = 105; greatNumberComputation(n); }} |
Python3
def count_pairs(arr, tar, size): lo, hi = 0, size - 1 check = False while lo < hi: if arr[lo] + arr[hi] == tar: check = True print(f"{arr[lo]} and {arr[hi]}") hi -= 1 elif arr[lo] + arr[hi] < tar: lo += 1 else: hi -= 1 if not check: print("No the given number is not a sum of two great numbers")def great_number_computation(n): arr = [] temp = 0 for i in range(n): temp += i * i if temp < n: arr.append(temp) else: break count_pairs(arr, n, len(arr))# Driver coden = 105great_number_computation(n) |
C#
using System;class Program{ // Function to find and print pairs of great numbers that sum up to the target static void CountPairs(int[] arr, int target, int size) { int lo = 0, hi = size - 1; bool check = false; while (lo < hi) { if (arr[lo] + arr[hi] == target) { check = true; Console.WriteLine(arr[lo] + " and " + arr[hi]); hi--; } else if (arr[lo] + arr[hi] < target) { lo++; } else { hi--; } } if (!check) Console.WriteLine("No, the given number is not a sum of two great numbers"); } // Function to compute great numbers and find pairs that sum up to the target static void GreatNumberComputation(int n) { var arr = new System.Collections.Generic.List<int>(); int temp = 0; for (int i = 0; temp < n; i++) { temp += i * i; arr.Add(temp); } int[] a = arr.ToArray(); CountPairs(a, n, arr.Count); } // Main driver function static void Main() { int n = 105; GreatNumberComputation(n); }} |
14 and 91
Time Complexity: O(N)
Auxiliary Space: O(N)
This article is contributed by Sanket Singh 2. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
