*Author*: Maaz Bin Asad

*Tester*: Prasoon Jain

*Editorialist*: Maaz Bin Asad

# DIFFICULTY

Easy

# PREREQUISITES

Observation skills

# PROBLEM:

Some integers can be represented as sum of consecutive integers. For instance, 3 can be represented as 1+2. Next integer is 6 which can be represented as 1+2+3 and so on. We need to find *Nth* integer that can be represented as sum of consecutive integers in this series. **Let’s say that integers is x**. After this, we need to find greatest integers that is smaller than

*x*and cannot be represented as sum of consecutive integers.

# Quick Explanation:

**Integers which are power of 2 cannot be represented as sum of consecutive integers**. Since, *Nth* integer won’t exceed 600, you can brute force to find greatest integer smaller than *Nth integer* that does not satisfy condition.

# Explanation:

After carefully observing from the sample test cases, it is clear that integers which are power of two cannot be represented as sum of consecutive integers. Since, *N* won’t be a big number, you can push first *N* integers that are not power of 2 in an array. The index of this array will represent *N*. After taking the input, you can store *Nth* integer from the array in a variable and iterate backwards from this integer. Whenever you encounter a number that is power of 2, store it in another variable and break the loop. Finally, just output XOR of both variables.

To check if a number of power of 2, you can use logarithm.

If \lfloor log(x) \rfloor=\lceil log(x) \rceil (log is taken with base 2), then given number is power of 2.

# TIME COMPLEXITY:

O(600): Creating array of numbers to query *Nth* integer.

O(*x*): To find the number that is power of 2 smaller than *x*.

# SOLUTIONS:

Tester’s Solution:

```
import java.util.ArrayList;
import java.util.Scanner;
class Xoring {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int t=sc.nextInt();
while(t>0) {
int n=sc.nextInt();
ArrayList<Integer> ar = new ArrayList<>();
//the numbers which are power of two are skipped
for(int i=1;i<=600;i++) {
if((i&(i-1))!=0) {
ar.add(i);
}
}
int nth=ar.get(n-1);
//last is the number which is power of two and is just before nth number.
int last=(int) ((double)Math.log(nth)/Math.log(2));
last=(int) Math.pow(2, last);
System.out.println(last^nth);
t--;
}
}
}
```