Question 2 (10 marks) Purpose: To practice accumulating values in a loop. Degree
ID: 3675871 • Letter: Q
Question
Question 2 (10 marks)
Purpose: To practice accumulating values in a loop.
Degree of Difficulty: Moderate
Write a program that asks the user for a positive integer N, and then uses that integer to compute
and display the following four sums and products:
1. The sum of integers 1 ... N inclusive.
2. The sum of the powers of 2: 20 + 21 + 22 + ... + 2(N-1)
3. The sum of the inverse of the powers of 2: 1/20 + 1/21 + 1/22 + ... + 1/2(N-1)
4. The product of the integers 1 ... N inclusive
Here is an example execution of the program with input 6 (the user inputs 6 in response to the
request "Input N: ", but the program displays everything else). Note that your output should be
formatted exactly as shown in the example below:
Input N: 6
1 + 2 + 3 + 4 + 5 + 6 = 21
1 + 2 + 4 + 8 + 16 + 32 = 63
1 + 0.5 + 0.25 + 0.125 + 0.0625 + 0.03125 = 1.96875
1 * 2 * 3 * 4 * 5 * 6 = 720
Make sure you test your program! Your program should work for any positive integer (i.e., greater
than 0)!
Hint: Do this question in stages. Get the first sum working perfectly (tested and everything!)
before going on to the second. You will cause yourself a lot of grief if you try to do this one all
at once. And you can use the ideas you develop from earlier parts to solve later parts.
Explanation / Answer
#include<iostream>
#include<conio>
#include<cmath>
using namespace std;
int sumOfDigitsFrom1ToN(int n)
{
// base case: if n<10 return sum of
// first n natural numbers
if (n<10)
return n*(n+1)/2;
// d = number of digits minus one in n. For 328, d is 2
int d = log10(n);
// computing sum of digits from 1 to 10^d-1,
// d=1 a[0]=0;
// d=2 a[1]=sum of digit from 1 to 9 = 45
// d=3 a[2]=sum of digit from 1 to 99 = a[1]*10 + 45*10^1 = 900
// d=4 a[3]=sum of digit from 1 to 999 = a[2]*10 + 45*10^2 = 13500
int *a = new int[d+1];
a[0] = 0, a[1] = 45;
for (int i=2; i<=d; i++)
a[i] = a[i-1]*10 + 45*ceil(pow(10,i-1));
// computing 10^d
int p = ceil(pow(10, d));
// Most significant digit (msd) of n,
// For 328, msd is 3 which can be obtained using 328/100
int msd = n/p;
// EXPLANATION FOR FIRST and SECOND TERMS IN BELOW LINE OF CODE
// First two terms compute sum of digits from 1 to 299
// (sum of digits in range 1-99 stored in a[d]) +
// (sum of digits in range 100-199, can be calculated as 1*100 + a[d]
// (sum of digits in range 200-299, can be calculated as 2*100 + a[d]
// The above sum can be written as 3*a[d] + (1+2)*100
// EXPLANATION FOR THIRD AND FOURTH TERMS IN BELOW LINE OF CODE
// The last two terms compute sum of digits in number from 300 to 328
// The third term adds 3*29 to sum as digit 3 occurs in all numbers
// from 300 to 328
// The fourth term recursively calls for 28
return msd*a[d] + (msd*(msd-1)/2)*p +
msd*(1+n%p) + sumOfDigitsFrom1ToN(n%p);
}
long long sumofpowersof2 (int N)
{ long long sum=1,p=1;
for(int i=1;i<N;i++)
{ sum= sum+ 2*p; p=p<<1; }
return sum;
}
void factorial(int n)
{
int res[MAX];
// Initialize result
res[0] = 1;
int res_size = 1;
// Apply simple factorial formula n! = 1 * 2 * 3 * 4...*n
for (int x=2; x<=n; x++)
res_size = multiply(x, res, res_size);
cout << "Factorial of given number is ";
for (int i=res_size-1; i>=0; i--)
cout << res[i];
}
// This function multiplies x with the number represented by res[].
// res_size is size of res[] or number of digits in the number represented
// by res[]. This function uses simple school mathematics for multiplication.
// This function may value of res_size and returns the new value of res_size
int multiply(int x, int res[], int res_size)
{
int carry = 0; // Initialize carry
// One by one multiply n with individual digits of res[]
for (int i=0; i<res_size; i++)
{
int prod = res[i] * x + carry;
res[i] = prod % 10; // Store last digit of 'prod' in res[]
carry = prod/10; // Put rest in carry
}
// Put carry in res and increase result size
while (carry)
{
res[res_size] = carry%10;
carry = carry/10;
res_size++;
}
return res_size;
}
long long sumofinversepowersof2 (int N)
{ long long sum=1,p=1;
for(int i=1;i<N;i++)
{ sum= sum+ 1/(2*p); p=p<<1; }
return sum;
}
int main()
{
int N;
cout<<"Input N:"<<endl;
cin>>N;
cout<<"Sum Of Integers upto N:"<<sumOfDigitsFrom1ToN(N);
cout<<" Sum Of Powers of 2( NTerms):"<<sumofpowersofN(N);
cout<<" Sum Of Inverse Powers of 2( NTerms):"<<sumofinverseof2(N);
cout<<" Product oF N Numbers";
factorial(N);
return 0;
}
}
Approaches Used:
Function 1
In general, we can compute sum(10d – 1) using below formula
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.