# Ad Rotation DSA Problem Solution In this post, we are going to solve Ad Rotation DSA Problem from JP Morgan Chase, Online Assessments conducted on 29th October,2022. Let’s have a look at the problem statement first and then try to solve the problem.

## Ad Rotation DSA Problem Statement

An e-commerce site has a series of advertisements to display. Links to the ads are stored in a data structure and they are displayed or not based on the value at a bit position in a number. The sequence of ads being displayed at this time can be represented as a binary value, where 1 means the ad is displayed and 0 means it is hidden. The ads should rotate, so on the next page load, ads that are displayed now are hidden and vice versa.

Given a base 10 integer representing the current display state of all ads, determine its binary representation. Starting from the position of its highest order 1 bit, negate that bit and all lower order bits from 0 to 1 or from 1 to 0. Return the base 10 representation of the result.

Input

The first line of input consists of a single integer

$n$$n$ the base 10 integer.

$\left(1\le n\le {10}^{5}\right)$$(1 \leq n \leq 10^5)$.

Output

The output should consist of a single integer

$-$$-$ the answer.

Examples
Input
50

Output
13

Input
100

Output
27


## Problem Solution in C++

#include <bits/stdc++.h>
using namespace std;

int main() {
int n;
cin>>n;
string s;
while(n>0){
if(n%2==0) s+="1";
else s+="0";
n/=2;
}
int num=0;
for(int i=0;i<s.size();i++){
num = num + (1<<i)*(s[i]-'0');
}
cout<<num<<endl;
return 0;
}

## Problem Solution in Python

def find_highest_bit(n):
# Find the position of the highest-order 1 bit
position = 0
while n:
position += 1
n >>= 1
return position

# Find the position of the highest-order 1 bit
highest_bit = find_highest_bit(n)

# Negate that bit and all lower order bits from 0 to 1 or from 1 to 0
result = n ^ ((1 << highest_bit) - 1)

return result

main()