Sum of numbers

All submissions for this problem are available.
According to folklore, the great mathematician Gauss was able to calculate the sum of the first 50 natural numbers in mere seconds. You are given a similar problem, where you have to calculate the sum of the first 'n' natural numbers. The only catch being that the the number 'n' can be really very large. You have to calculate the sum 1+2+...+n for a given value of 'n'.
Input
The first line consists of a number 't which specifies the number of test cases. 1<=t<=100. 't' lines follow with a number 'n' on each line. 'n' can have upto 20001 digits. 1<=n<=(10^20000).
Output
For each test case, output a number which represents the sum of the first 'n' natural numbers.
Example
Input: 2 3 5 Output: 6 15 Explanation The sum of the first 3 numbers is 1+2+3 = 6 The sum of the first 5 numbers is 1+2+3+4+5 = 15
Author:  admin 
Tags  admin 
Date Added:  22072009 
Time Limit:  22 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
hey people...I did this program in Java and it ran perfectly in BlueJ, but when I posted it here, it says compilation error.....please help.
Please read the FAQ and http://www.codechef.com/help/#hc_solinjav
The problem states that ['n' can have upto 20000 digits. 1<=n<=(10^20000).]. But 10^p yields p 1 digits, like 10^2=100, 10^3=1000, etc. So which condition is correct....if 'n' can have upto 20000 digits then 1<=n<=10^19999 or if 1<=n<=20000 then n can have upto 20001 digits?
i mean p 1
p plus 1 :)
This is fixed :)
ok... 1<=n<=20000 is the condition statement.
In Java, long integer datatype permits 18 digits and python permits unlimited number of digits. can C handle such long digits?
No, a native C data type can't handle such long numbers. You need a custom data type.
how come kevin's sol of 33s
See this post.
Pls help!!! <<Admin can u
Pls help!!! <<Admin can u help???>>
I made a code in Java on Netbeans and it was working !!! ;)
But after I submitted here it says wrong output !!!
Ne once can comment whts wrong with the code!!!
Thnxxxxx!!!
If you post your code in the
If you post your code in the forum then people other than admin can tell you what you have done wrong.
import java.io.* ; import
import java.io.* ;
import java.math.BigInteger;
/** @author Kunal Suri*/
public class Main {
static final BigInteger ONE = new BigInteger("1");
static final BigInteger TWO = new BigInteger("2");
public static void main(String[] args) {
InputStreamReader istream = new InputStreamReader(System.in) ;
BufferedReader bufRead = new BufferedReader(istream) ;
try
{
BigInteger N,N1,N2,N3;
System.out.println("Please Enter the Number (N): ");
String line = bufRead.readLine();
N = new BigInteger(line);
N1 = N.add(ONE);
N2 = N.multiply(N1);
N3 = N2.divide(TWO);
System.out.println("The sum of the first " + N + " numbers is :" + N3);}
catch (IOException e) { System.out.println("Error reading line");}
catch(NumberFormatException e) { System.out.println("Error Converting Number");}}}
Its based on Arithmetic
Its based on Arithmetic progression!!! I hope I m doin it correctly...
its like 1+2+3+...+n =>
sum = n(2*a1 + (n1)*d)/2.. where n is the no of digits ,a1 is the first digit and d is the difference..
In our case a1 = 1 always, d=1 always.. thus the equation become n*(n+1)/2
pls feel free to let me know
pls feel free to let me know where I am going wrong....
Thnx in Advance!!! ;)
The correct output for the
The correct output for the sample input is:
Your output is:
These are not exactly the same, so you get Wrong Answer.
#include<stdio.h>int
#include<stdio.h>
int solve(int n)
{
long int sum=0;
sum=(n*(n+1))/2;
return n;
}
int main()
{
int N,a[];
scanf("%d",&N);
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<N;i++)
{
prinf("%ld",solve(a[i]));
}
}
is it rite.??? how to solve
is it rite.???
how to solve for large number of digits...?
The formula is correct, but
The formula is correct, but it won't work for very large numbers. You might want to user some data structure to represent large numbers.
how to i/p large integer of
how to i/p large integer of 20000 digits..any clue...!!!
As a string.
As a string.
directi admin, i compiled
directi admin,
i compiled this program on my system and ran it took around 2s for input of the order of 10^20000
However when i submit it shows time limit exceeded.
Also during submission it says compile error, however later on it marks it as time limit exceeded.
Where sould i post my code for you to check it
Our servers might be slower
Our servers might be slower than your computer. You need a more efficient algorithm if the judge gives you a TLE.
well my system is just a P4
well my system is just a P4 and i dont think it would be slower than your servers. Even then a jump of 2s on my system to more than 22s on yours seems too large.
Don't forget there could be
Don't forget there could be 100 test cases.. is your program running 100 inputs of size 10^20000 in under 2 seconds or just one?
its running a single test
its running a single test case in under 2s
Therefore your solution could
Therefore your solution could take up to 200 seconds, which will exceed the time limit of 22 seconds. You'll need something much faster :)
@admin Please discourage the
@admin
Please discourage the writing of code snippet in the comments column and it will be nice if u can remove such comments.
I'm new user ..Admin,Canyou
I'm new user ..Admin,Canyou tell me,what's the error with my code ? It worked in my local system. Is it possible to check the errors ? or any other clues ?
hey i m getting time limit
hey i m getting time limit exceed
how to optimize the below code
#include<stdio.h>
#include<math.h>
int main()
{
int i,q;
unsigned long s,n[100];
scanf("%d",&q);
for(i=1;i<=q;i++)
scanf("%ld",&n[i]);
for(i=1;i<=q;i++)
{
s=n[i]+((pow(n[i],2))n[i])/2;
printf("n%ld",s);
}
return 1;
}
Your code suggests you
Your code suggests you clearly haven't read the input constraints.
Hi, I have submitted my
Hi,
I have submitted my solution which runs in under 13s on local machine for the worst case input of 100 numbers of 20000 digits each.(used time to measure runtime and input/ouput redirection was also in place)
Being a two year old machine I dont think the time difference between the online judge and my machine should be much.
my submission is : http://www.codechef.com/viewsolution/273626
Can anyone verify if my machine is really that fast, or if there is some problem with the judging here.
(Interestingly no successful submissions since Feb)
Hi while submitting the code
Hi
while submitting the code I am getting the run time error.can you help me to find the solution for this error. the codes, which I submitted below.
Read the FAQ. There are at
Read the FAQ. There are at least 3 separate problems with that code, all mentioned in the FAQ.
Somebody please check my
Somebody please check my solution,it takes not more than 14s in my machine to run 100 test cases in worst case of number having 20000 digits,but it shows TLE here :( !!!,please help.
Somebody please help!!!!!
Somebody please help!!!!!
I think you should use fast
I think you should use fast multiplication algorithms, with O(n * log(n)) or O(n^{log23}) coplexiety.
@zayakin I am using karatsuba
@zayakin
I am using karatsuba multiplication algorithm and it runs within 14s for 100 worst test cases,even then I am getting a TLE!
#/usr/bin/perl use
#/usr/bin/perl
use strict;
my $num = $ARGV[0];
my $sum = $num*($num+1)/2;
print " The sum of first n natural numbers is $sumn";
exit 0;
<p>import java.io.*; class
<p>import java.io.*;
class NewMain {
public static void main(String[] args) throws IOException {
BufferedReader in= new BufferedReader(new InputStreamReader(System.in));
int m= Integer.parseInt(in.readLine());
int nat[]=new int[m];
int res=0,sum=0;
for(int a=0; a<2*m; a++){
if(a<m){
nat[a]=Integer.parseInt(in.readLine());
}
else{
for(int l=1; l<=nat[am];l++)
{
sum=sum+l;
}
System.out.println(sum+"res");
sum=0;
}
}
}
}</P
//it is runnig in cmd bt site showing runtime error
need help for above
need help for above program... Its also running on IDE.... without error....
in maths : an arithmetic
in maths :
an arithmetic serie
sum = (n/2)*(1+n)
n is the number, eg if n=3 => sum = 3/2 * 4 = 6
but doesn't work !!!!1
import java.io.*; class
import java.io.*;
class NewMain {
public static void main(String[] args) throws IOException {
BufferedReader in= new BufferedReader(new InputStreamReader(System.in));
int m= Integer.parseInt(in.readLine());
int nat[]=new int[m];
int res=0,sum=0;
for(int a=0; a<2*m; a++){
if(a<m){
nat[a]=Integer.parseInt(in.readLine());
}
else{
for(int l=1; l<=nat[am];l++)
{
sum=sum+l;
}
System.out.println(sum+"res");
sum=0;
}
}
System.exit(0);
}
}
//Still not working after removing NZEC error
#include /*int sum(int
import
http://ideone.com/FHfFv see
The test cases are too much
if my program gives the wrong
can anybody help me what went
My solution takes less than 8
#include int main() { int