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.
The first line of input consists of a single integer
the base 10 integer.
.
The output should consist of a single integer
the answer.
50
13
100
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
def rotate_ads(n):
# 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
# Input reading
def main():
n = int(input())
result = rotate_ads(n)
print(result)
if __name__ == "__main__":
main()