5
\$\begingroup\$

I have written following code for the this C++ Problem:

Write a program to add only odd numbers between one to ten.

#include <iostream>

using namespace std;

int main()
{
    int num = 1, n = 0;
    int odd_num;
    while(num <= 10)
    {
        if(num % 2 != 0)
        {
          odd_num = num;
          odd_num += n;
          n = odd_num;
        }
        num++;
    }
    cout<<"Sum = "<<odd_num;
    return 0;
}

Please tell how I can improve this code .

\$\endgroup\$
1
  • 3
    \$\begingroup\$ odd_num is a lousy name (if you'd used 8 instead of 10, odd_num would end up being 16, which is odd (strange) to call odd (not even)). Better would be running_sum. \$\endgroup\$
    – Teepeemm
    Sep 27 at 18:20
22
\$\begingroup\$

using namespace std; is a poor practice and can be harmful, so it's good to rid yourself of that habit early on.

The loop's structure is

int num = 1;
while(num <= 10)
{
    ⋮
    num++;
}

That is more familiar to C++ programmers as a for loop:

for (int num = 1;  num <= 10;  ++num) {
    ⋮
}

odd_num shouldn't be necessary; it seems to be a temporary store for our total n, but we could just replace the three lines in the if with a simple n += num.

Instead of incrementing by 1 each iteration, then testing whether we have a multiple of 2, we can avoid the test if we increment by 2 each iteration.

Prefer short names for short-lived variables (e.g. loop counter) and longer, more descriptive names for variables with larger scope (e.g. our running total).

When we print the output, it's usual to write a whole line (ending in a newline character):

std::cout << "Sum = " << odd_num << '\n';

We are allowed to omit return 0; from main() (though not from any other function).

It may be useful to define a variable for the range of numbers we're considering (we might want to make that a program argument in future).


Modified code

#include <iostream>

constexpr int limit = 10;

int main()
{
    int total = 0;
    for (int n = 1;  n <= limit;  n += 2) {
        total += n;
    }
    std::cout << "Sum = " << total << '\n';
}

Closed-form solution

Some simple mathematics could allow us to determine the sum algebraicly, without using a loop. In real code, we would prefer the closed form (with suitable comment), but this seems to be practice code where the objective is to improve your loop logic, so I'm not proposing that right now.

However, if you do want to follow this idea, it's fairly simple. Consider that we have 1 + 3 + ... + 7 + 9. If we pair 1 with 9, we get 10, or 5 + 5, giving us 5 + 3 + ... + 7 + 5; now pair 3 with 7, and so on, giving us 5 + 5 + ... + 5 + 5. We just need to work out how many 5s to multiply. See if you can work out a general formula to calculate this sum for any range of odd integers.

Hint: we'll probably want make the range exact (e.g. by rounding the start and end to both be odd numbers) before applying a general formula.


Testing

A good way to approach the closed-form solution is to split the program, to create a function that can be independently tested. That would look like this:

int sum_of_odd_numbers(int min, int max)
{
    ⋮
}

We can then test it with different values. The simplest way is with asserts in main(); alternatively, use one of the available unit-test libraries to get better diagnostics from failing tests (and lots of other useful features).

Here's values I tested with:

#include <cassert>

int main()
{
    // range 1-10 (from question)
    assert(sum_of_odd_numbers(1, 10) == 25);
    assert(sum_of_odd_numbers(0, 10) == 25);
    assert(sum_of_odd_numbers(0, 9) == 25);

    // trivial ranges
    assert(sum_of_odd_numbers(0, 0) == 0);
    assert(sum_of_odd_numbers(2, 2) == 0);
    assert(sum_of_odd_numbers(1, 1) == 1);
    assert(sum_of_odd_numbers(-1, -1) == -1);
    assert(sum_of_odd_numbers(3, 3) == 3);

    // simple ranges
    assert(sum_of_odd_numbers(0, 3) == 4);
    assert(sum_of_odd_numbers(3, 5) == 8);
    assert(sum_of_odd_numbers(-1, 1) == 0);
    assert(sum_of_odd_numbers(-3, -1) == -4);
    assert(sum_of_odd_numbers(-3, 1) == -3);
}

And the closed-form calculation:

int sum_of_odd_numbers(int min, int max)
{
    // N.B. we assume the arithmetic doesn't overflow
    if (min % 2 == 0) {
        ++min;
    }
    if (max % 2 == 0) {
        --max;
    }
    return (max + min) * (max - min + 2) / 4;
}
\$\endgroup\$
10
  • \$\begingroup\$ Thank you for reviewing . Can you explain why using namespace std is a wrong habit. Also why you have used constexper ? I'm not familiar to constexpr. \$\endgroup\$ Sep 26 at 13:35
  • \$\begingroup\$ Why is "using namespace std;" considered bad practice?. constexpr is pretty much like const here, but it's a little stronger and allows us to use the variable for things that need to be compile-time constant expressions such as array dimensions. const would be fine for this program. \$\endgroup\$ Sep 26 at 13:44
  • 2
    \$\begingroup\$ The last hint is likely to complicate the life of anyone that isn't familiar with bit twiddling, the compiler will convert the more understandable (n/2)*2 and (n/2)*2+1 to the bit functions itself, see godbolt.org/z/rcYnxfh44 . \$\endgroup\$
    – 12345ieee
    Sep 26 at 22:39
  • 3
    \$\begingroup\$ An intermediary step between "run a loop and test if num is odd at every step" and "calculate the sum algebraically" could be "run a loop, but increment 2 by 2 so you only see odd numbers" \$\endgroup\$
    – Stef
    Sep 27 at 16:18
  • 1
    \$\begingroup\$ @12345ieee: But note you had to use unsigned int for that optimization to be legal because C signed division rounds rounding towards 0 instead of -infinity. This code is using signed int, making the range possibly include negative numbers, and the compiler has to make asm that works for any input. You'd get wrong answers like up_to_odd(-3) == -1. If you'd used a right shift (on a C++ implementation where that's an arithmetic right shift), you'd be ok and compilers can optimize. godbolt.org/z/zs6E7nTnc. n | 1 or n &= -2 do work for this for 2's complement implementations. \$\endgroup\$ Sep 27 at 20:06
8
\$\begingroup\$

Use functions

Always define the task as functions (method) to make the code portable and give it more semantic meaning via the functions name.

If you define the task as a function keep roles separate. The task of summing odd values should not display the result, it only returns the sum.

If the task is to display the sum of odd values between 1 and 10 then you would not need any calculations as the value is a constant 25. So rather redefine the task to sum odd value between any two integers.

While loops

There is nothing wrong with using while loops. Many times while loops require less code making the code more readable and easier to maintain.

Example

The function SumOdd returns an int that is the sum of odd values between min and max inclusive.

#include <iostream>

int SumOdd(int min, int max)  {
    int val = min + ((abs(min) + 1) % 2);  // start at closest odd >= min
    int sum = 0;   
    while (val <= max) {
        sum += val;
        val += 2;
    }
    return sum;
}

int main() {
    std::cout << "Sum = " << SumOdd(-3, 10) << std::endl;
    return 0;
}

however this has some serious problems / limits...

  • The sum can be greater than 32bit int can hold. Max sum between any two 32bit integers is ~1.2 quintillion, well above the max value for a 32 bit int.
  • When the difference between min and max is very large it will take a long time to complete (at worst ~2.1 billion iterations)

Use a 64bit int

To fix the first problem we can make the sum a 64 bit int long long

Don't brute force it

To fix the second is a little more complicated as the value is an int which can have a sign. The formula \$((1+n)/2)^2\$ to sum odd values doe not work if some values are negative. Nor does it work if the we start summing above 1.

To get the sum between any two values we need to calculate the sum from 0 to max and to min, and then sum those values correctly setting the sign depending on the sign of input arguments.

Thus we get

long long SumOdd(int min, int max)  {    
    long long halfMax, halfMin;
    if (max < min || max == -min) { return 0; }
    if (max == min) { return abs(min % 2) == 1 ? (long long) min : 0; }    
    if (min < 0) {
        halfMin = (long long) ((1 - min) / 2);
        halfMax = (long long) (max < 0 ? (1 - max) / 2 : (1 + max) / 2);
        return -halfMin * halfMin + halfMax * halfMax;
    }
    halfMin = (long long) ((1 + min) / 2);
    halfMax = (long long) ((1 + max) / 2);
    return halfMax * halfMax - halfMin * halfMin;
}

Note that long long defines a signed (at least) 64 bit int. The int is automatically added to make long long int

\$\endgroup\$
4
  • \$\begingroup\$ Surprised you didn't discuss how your code optimizes away the if inside the loop by incrementing by 2. That's a good general thing to look for, iterating over interesting values rather than iterating everything and checking with an if. I guess it kind of speaks for itself in the simplicity, though. \$\endgroup\$ Sep 27 at 16:41
  • \$\begingroup\$ Toby's answer points out that n | 1 rounds upwards to the next odd number. For negative numbers, this works for 2's complement (e.g. consider setting the low bit in -2 to make -1). And I guess also sign/magnitude, but not 1's complement. However, modern ISO C++ is planning to drop support for non-2's-complement implementations. So it's at least worth mentioning, since the (abs + 1) % 2 way is harder to think through and verify correct. But it doesn't depend on binary number representations, just arithmetic operations. However, abs has signed-overflow UB on INT_MIN. \$\endgroup\$ Sep 27 at 16:44
  • \$\begingroup\$ Fun fact: clang can optimize the loop safely into closed-form asm. Oh, but not with the start and end both variable, it seems. godbolt.org/z/P193f1YM1. (Also included a min|1 version to show it compiles nicely.) \$\endgroup\$ Sep 27 at 16:50
  • \$\begingroup\$ @Blindman67 I have not learnt abt functions in C++ yet. But thanks your answer is very informative. \$\endgroup\$ Sep 28 at 6:33
4
\$\begingroup\$

Using using to bring function to into scope.

Like already mentioned by @Toby Speight using namespace std; is a bad habit. With using you can bring only std::cout into the scope.

#include <iostream>

int main(){
   using std::cout;
   cout << "..."; // Fine to use as we brought std::cout to main function's scope.
                 // Not polluting the global scope.
}

Bitwise & the number with 1

Every odd number has the LSB set to 1. To check if a bit is set bitwise & with 1. If the result is 1 then the bit is set. If the bit is not set the result is 0.

Decimal Binary
1 0b1
3 0b11
5 0b101
7 0b111
9 0b1001
#include <cstddef> // for size_t
for(size_t i=1; i < 10; ++i){
    if (i&1) total += i;
}

The bitwise trick seems like an unnecessary and premature optimization. Any decent compiler will optimize it to a bitwise AND on its own. num % 2 == 1 is more intuitive than num & 1 - Rish

Increment loop by 2

We all know odd and even numbers alternate with each other.

int total = 0
for(size_t i=1; i < 10; i = i+2){
   // i -> is always odd
   total += i;
}

Math based approach

Sum of \$N\$ odd numbers(1+3+5+7...): $$\sum_{k=0}^N (2k+1) = N^2$$

You need to find how many odd numbers are there between 1 to 10. You can generalize this approach to find the number of odd numbers b/w the range [1, L] using the logic that odd and even number alternate with each other.

\$\endgroup\$
6
  • 7
    \$\begingroup\$ The bitwise trick seems like an unnecessary and premature optimization. Any decent compiler will optimize it to a bitwise AND on its own. num % 2 == 1 is more intuitive than num & 1 \$\endgroup\$
    – Rish
    Sep 26 at 20:49
  • \$\begingroup\$ @Rish Yes, makes sense thank you. I'll strike that part. \$\endgroup\$
    – Ch3steR
    Sep 27 at 4:04
  • 2
    \$\begingroup\$ Agh - I meant to suggest changing the loop increment to 2, then completely forgot to mention it! I'm glad you wrote that suggestion, to close the hole. \$\endgroup\$ Sep 27 at 6:55
  • 1
    \$\begingroup\$ I suggest parentheses in your math formula. \sum_{k=0}^N (2k+1) and (\sum_{k=0}^N 2k)+1 are not the same quantities. \$\endgroup\$
    – Stef
    Sep 27 at 16:23
  • 2
    \$\begingroup\$ @Rish: num % 2 is negative for negative integers, so the actual expression you want is num % 2 != 0 like the question is using. num % 2 == 1 on signed int requires the compiler to care about the sign bit as well. What is the fastest way to find if a number is even or odd? Of course if you don't generalize this function like Blindman67's answer did, the compiler can prove that num will be non-negative and can optimize to just a bitwise test. But in general as a habit, write odd/even tests as num % 2 !=0 unless you want to reject negative \$\endgroup\$ Sep 27 at 16:55
0
\$\begingroup\$

Maybe you could increment n by 2 instead of 1 to reduce the number of cycles when you get the first odd value. I know it may sound stupid and overengineered but your code was already fine.

\$\endgroup\$
2
  • \$\begingroup\$ Just curious, did you read the other answers on this question? There were a couple of problems in the code. \$\endgroup\$
    – pacmaninbw
    Sep 27 at 10:50
  • 1
    \$\begingroup\$ The other answers already include this suggestion. \$\endgroup\$
    – JDługosz
    Sep 27 at 15:48
0
\$\begingroup\$

Create a single Sum function that can accept any kind of predicate. If you want to find the sum of all odd elements, pass IsOdd function to it as follows.

Sum(&IsOdd, data)

where data is a vector of int.

For more details, see the complete code below.

#include <iostream>
#include <vector>
#include <cmath>


typedef bool (*Predicate)(int);

int Sum(Predicate f, std::vector<int> data)
{
    size_t N = data.size();
    int sum = 0;
    for (int i = 0; i < N; ++i)
        if (f(data[i]))
            sum += data[i];
    return sum;
}

bool IsOdd(int x)
{
    return x % 2 == 1;
}

bool IsEven(int x)
{
    return x % 2 == 0;
}

bool IsPrime(int x)
{
    if (x < 2)
        return false;
    if (x == 2)
        return true;
    if (x % 2 == 0)
        return false;

    int N = (int)std::sqrt(x);
    for (int i = 2; i < N; i = i + 2)
        if (x % (i + 1) == 0)
            return false;

    return true;
}

int main()
{
    std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 49};
    std::cout << "The total sum of prime elements: " << Sum(&IsPrime, data) << "\n";
    return 0;
}
\$\endgroup\$
-2
\$\begingroup\$

Using namespaces imports the said namespace globally into your code file, in this case you are importing the standard library.

Let's say you have another custom namespace providing a function cout what will happen then.

Namespace Collision

Here your code will be confused on which function it can call, hence it will call them both leaving you with unwanted results.

Also, the statement std::cout adds clarity to your code as here you are aware that the cout belongs to the standard library.

For the answer to your question...

Yes, your code can be shorter using these 2 ways: (PS: Both of them use mathematics)

Here limit variable essentially asks, how many odd numbers you want to add? If you say 10 then it means add first 10 odd numbers not the odd numbers till 10...

First approach

#include <iostream>

/*
 * This method uses the formula (2 x n + 1) with a sign modification.
 * There n denotes the odd number at nth place and n = 0, 1, 2...
 * eg: if n = 2 then the odd number is 5 and sum till n is 9
 */

int main(){
    int limit = 10, oddSum = 0;
    
    // Here you set a limit... i.e: The value of n
    // Notice we are subtracting one from the limit
    // Hence the value of n or limit ranges from 1, 2, 3, 4.....
    /*
     * limit << 1 is a right shift operation which is an efficient way 
     * of saying limit * 2, as right shift operation multiplies the 
     * number given by 2
     */

    for(limit = limit; limit > 0; limit--)
        oddSum += (limit << 1) - 1;
    
    // Wola! You are done now print the sum
    // Yes, mathematics is important in coding

    std::cout << oddSum << std::endl;
}

Second approach

Here pow is a function in math.h

It will raise the limit i.e n to the said exponent

Please don't use it for squares, I added it so that you might learn a useful function.

pow(value, exponent)... Fancy way of saying n2

#include <iostream>

#include <math.h>

/*
 * Using mathematics we can always see that the sum of n odd numbers
 * is the square of itself... 
 * This result makes the problem very simple
 */

int main(){
    int limit = 10, oddSum = pow(limit, 2);

    // Boom! You are done now print the sum

    std::cout << oddSum << std::endl
}

Approach without mathematics

First Approach

#include <iostream>

int main(){
    int limit, oddNumber = 1, oddSum = 0;

    for (limit = 10; limit > 0; limit-- && (oddNumber = oddNumber + 2))
        oddSum += oddNumber;

    std::cout << oddSum << std::endl;
    
}

Second Approach

Here limit means add all odd numbers till the number limit. If limit = 10 then add 1, 3, 5, 7, 9...

#include <iostream>

int main(){
    int limit, oddSum = 0;

    for (limit = 10; limit > 0; limit--)
        oddSum = (limit % 2 != 0) ? (oddSum + limit): oddSum;

    std::cout << oddSum << std::endl;
}

Third Approach

Here the meaning of limit is same as the previous approach...

#include <iostream>

int main(){
    int limit = 10, oddNumber, oddSum = 0;

    for (oddNumber = 1; oddNumber <= limit; oddNumber = oddNumber + 2)
        oddSum += oddNumber;

    std::cout << oddSum << std::endl;
}

Increasing the variable range from int to long or long long will increase the number of values you can calculate... No need to overkill such a simple problem with methods. Its like bringing machine guns to a knife fight.

Ohh! And please don't use std::endl on every line... It flushes out the buffer which is an expensive call. Use it at the end or if performance is necessary don't use it at all.

Edit:

I had some free time from my own personal projects, college projects and assignments. Therefore, I went over your problem of odd sums...

If you have read this answer thoroughly, then you might wonder.. Why do the last 2 solutions change the definition of the variable limit?

I wanted to give you and comments a simplified solution using loops and the initial approach of people when solving this problem. There are many complicated ways in which you can solve this problem, for example add in hash maps and mem sets, you will find some very different codes in either cases.

This means you can even use dynamic programming and backtracking on such a simple problem... Why? Just so that you can calculate values larger than what long long can hold, while also calculating their sum. Then again as I said, this will be similar to killing an ant with 100 ballistic missiles.

You might wonder why have I approached this problem using simple and concise codes? It is because of time complexity... Here in all the solutions not only including my answers but other as well, the solution which uses another overkill function pow will run the fastest for any values that fit under long long.

Then how do I solve, when the definition of the variable limit changes for the last 2 approaches in my answer?

There is another efficient way using maths...

The odd numbers is a series values from 1 to infinity...

That is: 1, 3, 5, 7, 9, 11, 13.... and so on.

You know that using the formula 2*n - 1 you can find any odd number at any given position in the series... Here n ranges from 1 to infinity.

That is, n can be any number in this series: 1, 2, 3, 4, 5, 6... infinity.

Using mathematics again you can find the position (n) of any given odd number, if you do so then you simply square the position (n) of it to obtain the sum of odd number till the given odd number. Thus also answering the problem of finding a better way to solve for the last 2 approaches.

Enough blabbering here is the code:

#include <iostream>

int main() {
    int limit = 10, n = 0, oddSum = 0;
    
    // Check if the given limit is even if yes then subtract 1 to make it odd

    limit = (limit % 2 == 0) ? limit - 1: limit;
    
    // Now calculate the position (n)
   
    n = (limit + 1) / 2;

    // Now calculate the sum

    oddSum = n * n;

    // Print the sum

    std::cout << "The sum of odd numbers is " << oddSum

    // No std::endl here and the time complexity should be O(1) if I am correct

    // This will net you say for limit = 10 the oddSum will be 25
     
}
\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.