How to check if a really big number is a continuous sum from 1?-CodePudding

I am trying to solve this problem: check if the element of an array is a continuous sum from 1. Input Q (length of array, 1≤Q≤10^3), then Input elements based on length (1≤N[i]≤10^18). Example: 6=1 2 3 print Yes. 10=1 2 3 4 print Yes. 5=2 3 print No cause it not continuous sum from 1 Things are my code work on a small number for example 6, 10, 15. But I also need to check the bigger ones based on condition (like 234223743). How can I simpler my code ? My code:

import java.util.Scanner; 

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int sum =0;
        int x=1;
        int Q = scanner.nextInt();
        int []N=new int [Q];
        for (int i = 0 ; i<Q;i  ){
            N [i]= scanner.nextInt();
            while (sum <N[i]){
                sum = sum x;
                x  ;
            }
            if (sum==N[i]){
                System.out.println("YES");
            }
            else{
                System.out.println("NO");
            }
            sum=0;  
            x=1;
        }
        
        scanner.close();
        
    }

CodePudding user response：

Math works here. You can use the quadratic equation solution. The sum of first N natural numbers is n*(n 1)/2. So basically

⇾ 1   2   3   …. N =  S
⇾ (N * (N   1)) /  2 = S
⇾ N * (N   1) = 2 * S
⇾ N2    N  – 2 * S = 0

We know your s here so just solve the quadratic equation. Something like

import java.util.Scanner; 

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int sum =0;
        int x=1;
        int Q = scanner.nextInt();
        int []N=new int [Q];
        for (int i = 0 ; i<Q;i  ){
            N [i]= scanner.nextInt();

            // Solution of Quadratic Equation
            double k = (-1.0   Math.sqrt(1   8 * N[i])) / 2;
           
            // Condition to check if the
            // solution is a integer
            if (Math.ceil(k) == Math.floor(k))
              System.out.println("YES");
            else
              System.out.println("NO");
        }
        
    }

This page has a binary search solution also if you are interested. https://www.geeksforgeeks.org/find-given-number-sum-first-n-natural-numbers/