Styjun

Consider a permutation of numbers 1 to n written on a paper. Let’s denote the product of its element as p and the sum of its elements as s. Given a positive integer n, your task is to determine whether p is divisible by s or not.

i tried by using bigInteger concept but out of 50 test case 30 is successfully passed but rest of them are showing timeout which may be because of recursion.

import java.util.*;
import java.math.BigInteger;

public class TestClass 
 static BigInteger factorial(int n)

 public static void main(String args[] ) throws Exception 
 Scanner s=new Scanner(System.in);
 int n=s.nextInt();
 int nn=n*(n+1)/2;
 BigInteger sum=BigInteger.valueOf(nn);
 BigInteger p=factorial(n); 

 if((p.mod(sum)).equals(BigInteger.valueOf(0)))
 System.out.println("YES");
 else
 System.out.println("NO");
 

for the sample test case is like
input is 3 and its output should be "YES".since (1+2+3) divides (1*2*3).

Try to remove the recursion and use the for loop to calculate the factorial.

import java.util.*;
import java.math.BigInteger;
public class TestClass 
static void factorial(long n, long nn)

 BigInteger answer=new BigInteger("1");
 BigInteger sum=BigInteger.valueOf(nn);
 int foundMatch =0;
 for(long i=n;i>0;i--)
 answer=answer.multiply(new BigInteger(String.valueOf(i)));
 if((answer.mod(sum)).equals(BigInteger.valueOf(0)))
 
 System.out.println("YES");
 foundMatch = 1;
 break;
 
 
 if(foundMatch!=1)
 System.out.println("NO");


public static void main(String args[] ) throws Exception 
 Scanner s=new Scanner(System.in);
 long n=s.nextLong();
 long nn=n*(n+1)/2;

 factorial(n, nn); 

You can use the logic that if the intermediate product of the factorial is divisible by the sum, then the entire factorial is also divisible by sum.

import java.math.BigInteger;
import java.util.Scanner;

public class TestClass 
static boolean isFactorialDivisible(int n, BigInteger sum) 
 BigInteger p = BigInteger.ONE;
 for (int i = n; i > 0; i--) 
 p = p.multiply(BigInteger.valueOf(n));
 if (p.mod(sum).equals(BigInteger.ZERO)) 
 return true;
 
 BigInteger gcd = p.gcd(sum);
 if (!gcd.equals(BigInteger.ONE)) 
 p = p.divide(gcd);
 sum = sum.divide(gcd);
 
 
 return false;


public static void main(String args[]) throws Exception 
 Scanner s = new Scanner(System.in);
 int n = s.nextInt();
 int nn = n * (n + 1) / 2;
 BigInteger sum = BigInteger.valueOf(nn);
 boolean p = isFactorialDivisible(n, sum);
 if (p)
 System.out.println("YES");
 else
 System.out.println("NO");

import java.util.*;
class TestClass 
 public static int prime(int n)
 
 int count=0,flag=0;
 if(n==1)
 flag=1;
 if(n==2)
 flag=0;
 else 
 for(int i=2;i<=Math.sqrt(n);i++) 
 if(n%i==0)
 
 flag=1;
 break;
 
 
 if(flag==1)
 return 1;
 return 0;

 
 public static void main(String args[] ) throws Exception 
 Scanner s=new Scanner(System.in);
 int t=s.nextInt();
 while(t-->0)
 
 int flag=0;
 int n=s.nextInt();
 if(n%2==0)
 
 flag=prime(n+1); 
 
 else
 
 flag=1;
 
 if(flag==1)
 System.out.println("YES");
 else
 System.out.println("NO");