# Count integers up to N which can be represented as sum of two or more consecutive numbers

Given a positive integer **N**, the task is to count the number of integers upto **N** which can be represented as the sum of two or more consecutive numbers.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:N = 7Output:4Explanation:In the range [1, 7]: {3, 5, 6, 7} can be represented as sum of consecutive numbers.

- 3 = 1 + 2
- 5 = 2 + 3
- 6 = 1 + 2 + 3
- 7 = 3 + 4

Input:N = 15Output:11

**Naive Approach:** Follow the steps below to solve the problem:

- Iterate over all integers in the range
**[1, N]**and for each integer, check if it can be represented as the sum of two or more consecutive integers or not. - To check whether a number can be expressed as the sum of two or more consecutive numbers or not, refer to this article.

Below is the implementation of the above approach:

## C++

`// C++ Program to implement` `// the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to check if the number N` `// can be expressed as sum of 2 or` `// more consecutive numbers or not` `bool` `isPossible(` `int` `N)` `{` ` ` `return` `((N & (N - 1)) && N);` `}` `// Function to count integers in the range` `// [1, N] that can be expressed as sum of` `// 2 or more consecutive numbers` `void` `countElements(` `int` `N)` `{` ` ` `// Stores the required count` ` ` `int` `count = 0;` ` ` `for` `(` `int` `i = 1; i <= N; i++) {` ` ` `if` `(isPossible(i))` ` ` `count++;` ` ` `}` ` ` `cout << count;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 15;` ` ` `countElements(N);` ` ` `return` `0;` `}` |

## Java

`// Java program of the above approach` `import` `java.io.*;` `class` `GFG` `{` `// Function to check if the number N` `// can be expressed as sum of 2 or` `// more consecutive numbers or not` `static` `int` `isPossible(` `int` `N)` `{` ` ` `return` `(((N & (N - ` `1` `)) & N));` `}` `// Function to count integers in the range` `// [1, N] that can be expressed as sum of` `// 2 or more consecutive numbers` `static` `void` `countElements(` `int` `N)` `{` ` ` ` ` `// Stores the required count` ` ` `int` `count = ` `0` `;` ` ` `for` `(` `int` `i = ` `1` `; i <= N; i++)` ` ` `{` ` ` `if` `(isPossible(i) != ` `0` `)` ` ` `count++;` ` ` `}` ` ` `System.out.println(count);` `}` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `N = ` `15` `;` ` ` `countElements(N);` `}` `}` `// This code is contributed by jana_sayantan.` |

## Python3

`# Python3 Program to implement` `# the above approach` `# Function to check if the number N` `# can be expressed as sum of 2 or` `# more consecutive numbers or not` `def` `isPossible(N):` ` ` `return` `((N & (N ` `-` `1` `)) ` `and` `N)` `# Function to count integers in the range` `# [1, N] that can be expressed as sum of` `# 2 or more consecutive numbers` `def` `countElements(N):` ` ` ` ` `# Stores the required count` ` ` `count ` `=` `0` ` ` `for` `i ` `in` `range` `(` `1` `, N ` `+` `1` `):` ` ` `if` `(isPossible(i)):` ` ` `count ` `+` `=` `1` ` ` `print` `(count)` ` ` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `N ` `=` `15` ` ` `countElements(N)` ` ` `# This code is contributed by mohit kumar 29` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG` `{` `// Function to check if the number N` `// can be expressed as sum of 2 or` `// more consecutive numbers or not` `static` `int` `isPossible(` `int` `N)` `{` ` ` `return` `(((N & (N - 1)) & N));` `}` `// Function to count integers in the range` `// [1, N] that can be expressed as sum of` `// 2 or more consecutive numbers` `static` `void` `countElements(` `int` `N)` `{` ` ` ` ` `// Stores the required count` ` ` `int` `count = 0;` ` ` `for` `(` `int` `i = 1; i <= N; i++)` ` ` `{` ` ` `if` `(isPossible(i) != 0)` ` ` `count++;` ` ` `}` ` ` `Console.Write(count);` `}` `// Driver Code` `static` `public` `void` `Main()` `{` ` ` `int` `N = 15;` ` ` `countElements(N);` `}` `}` `// This code is contributed by code_hunt.` |

## Javascript

`<script>` `// JavaScript program of the above approach` ` ` `// Function to check if the number N` ` ` `// can be expressed as sum of 2 or` ` ` `// more consecutive numbers or not` ` ` `function` `isPossible(N) {` ` ` `return` `(((N & (N - 1)) & N));` ` ` `}` ` ` `// Function to count integers in the range` ` ` `// [1, N] that can be expressed as sum of` ` ` `// 2 or more consecutive numbers` ` ` `function` `countElements(N) {` ` ` `// Stores the required count` ` ` `var` `count = 0;` ` ` `for` `(i = 1; i <= N; i++) {` ` ` `if` `(isPossible(i) != 0)` ` ` `count++;` ` ` `}` ` ` `document.write(count);` ` ` `}` ` ` `// Driver Code` ` ` ` ` `var` `N = 15;` ` ` `countElements(N);` `// This code contributed by Rajput-Ji` `</script>` |

**Output:**

11

**Time Complexity: **O(N)**Auxiliary Space:** O(1)

**Efficient Approach: **To optimize the above approach, follow the steps below to solve the problem

- All numbers except the ones which are powers of 2 can be expressed as a sum of consecutive numbers.
- Count the number of powers of 2 â‰¤
**N**and store it in a variable, k say**Count** - Print
**(N – Count)**as the required answer.

Below is the implementation of the above approach:

## C++

`// C++ implementation` `// of the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to count integers in the range` `// [1, N] that can be expressed as sum of` `// 2 or more consecutive numbers` `void` `countElements(` `int` `N)` `{` ` ` `int` `Cur_Ele = 1;` ` ` `int` `Count = 0;` ` ` `// Count powers of 2 up to N` ` ` `while` `(Cur_Ele <= N) {` ` ` `// Increment count` ` ` `Count++;` ` ` `// Update current power of 2` ` ` `Cur_Ele = Cur_Ele * 2;` ` ` `}` ` ` `cout << N - Count;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 15;` ` ` `countElements(N);` ` ` `return` `0;` `}` |

## Java

`// Java implementation` `// of the above approach` `import` `java.util.*;` `class` `GFG` `{` ` ` `// Function to count integers in the range` ` ` `// [1, N] that can be expressed as sum of` ` ` `// 2 or more consecutive numbers` ` ` `static` `void` `countElements(` `int` `N)` ` ` `{` ` ` `int` `Cur_Ele = ` `1` `;` ` ` `int` `Count = ` `0` `;` ` ` `// Count powers of 2 up to N` ` ` `while` `(Cur_Ele <= N)` ` ` `{` ` ` `// Increment count` ` ` `Count++;` ` ` `// Update current power of 2` ` ` `Cur_Ele = Cur_Ele * ` `2` `;` ` ` `}` ` ` `System.out.print(N - Count);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `N = ` `15` `;` ` ` `countElements(N);` ` ` `}` `}` `// This code is contributed by shikhasingrajput` |

## Python3

`# python 3 implementation` `# of the above approach` `# Function to count integers in the range` `# [1, N] that can be expressed as sum of` `# 2 or more consecutive numbers` `def` `countElements(N):` ` ` `Cur_Ele ` `=` `1` ` ` `Count ` `=` `0` ` ` `# Count powers of 2 up to N` ` ` `while` `(Cur_Ele <` `=` `N):` ` ` `# Increment count` ` ` `Count ` `+` `=` `1` ` ` `# Update current power of 2` ` ` `Cur_Ele ` `=` `Cur_Ele ` `*` `2` ` ` `print` `(N ` `-` `Count)` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `N ` `=` `15` ` ` `countElements(N)` |

## C#

`// C# implementation` `// of the above approach` `using` `System;` `public` `class` `GFG` `{` ` ` `// Function to count integers in the range` ` ` `// [1, N] that can be expressed as sum of` ` ` `// 2 or more consecutive numbers` ` ` `static` `void` `countElements(` `int` `N)` ` ` `{` ` ` `int` `Cur_Ele = 1;` ` ` `int` `Count = 0;` ` ` `// Count powers of 2 up to N` ` ` `while` `(Cur_Ele <= N)` ` ` `{` ` ` `// Increment count` ` ` `Count++;` ` ` `// Update current power of 2` ` ` `Cur_Ele = Cur_Ele * 2;` ` ` `}` ` ` `Console.Write(N - Count);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` `int` `N = 15;` ` ` `countElements(N);` ` ` `}` `}` `// This code is contributed by 29AjayKumar` |

## Javascript

`<script>` `// Javascript implementation` `// of the above approach` `// Function to count integers in the range` `// [1, N] that can be expressed as sum of` `// 2 or more consecutive numbers` `function` `countElements(N)` `{` ` ` `var` `Cur_Ele = 1;` ` ` `var` `Count = 0;` ` ` `// Count powers of 2 up to N` ` ` `while` `(Cur_Ele <= N)` ` ` `{` ` ` ` ` `// Increment count` ` ` `Count++;` ` ` `// Update current power of 2` ` ` `Cur_Ele = Cur_Ele * 2;` ` ` `}` ` ` `document.write(N - Count);` `}` `// Driver Code` `var` `N = 15;` `countElements(N);` `// This code is contributed by todaysgaurav` `</script>` |

**Output:**

11

**Time Complexity:** O(log(N))**Auxiliary Space: **O(1)