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--;
}
}
}