Entering edit mode

Click here to Practice

Submit Problem to OJ

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.

**Example:**

*base10 = 30*

30 base 10 = 00011110 base 2

Strip the insignificant zeros then flip all of the bits in 11110 base 2 to get 00001 base 2 = 1 base 10. The example shows the value as an 8-bit binary to demonstrate that preceding zeros are discarded.

**Function Description**

Complete the function changeAds in the editor below.

changeAds has the following parameter:

*int base 10:* an integer in base 10

Return:

*int:* the base 10 value of the resulting binary

**Constraints**

- O <= base10 <= 10^5

Input Format for Custom Testing

**Sample Case 0**

**Sample Input**

**STDIN**

50

**Function**

base10 = 50

**Sample Output**

13

**Sample Case 1**

**Sample Input**

**STDIN**

100

**Function**

base10 = 100

**Sample Output**

27

Click here to Practice

Submit Problem to OJ

There is an array of integers, arr, and an integer value X. For each element in another array of integers, query_values, return the 1-based index in arr of the query_values[i] occurrence of X. If X does not occur query_values[i] times, return -1 for that query.

**Example**

arr = [1, 2, 20, 8, 8, 1, 2, 5, 8, 0]

X =8

query_values = [100, 4, 2]

There is no 100th or 4th instance of X = 8 in arr. The 2nd occurrence is at index 5. Return [-1,-1, 5].

**Function Description**

Complete the function kthOccurrence in the editor.

kthOccurrence has the following parameter(s):

int X: the integer to search for

int arr[n] : the elements to search

int query_values[q]: the occurrence of X to find the index of

**Returns** int[q]: the index in arr or -1 for each query

**Constraints**

- 1 <= n,q <= 2*10^5
- 0 <= arr, X, query_values <= 10^9

Entering edit mode

**Overview**

- Given an array of integers
**arr**and an integer value**X**. - Given another array of
**query_values**, we have to return 1-based index in**arr**of the**query_values[i] occurence**of X.

**Solution**

- Initialize an empty vector vx.
- Iterate over the array arr and whenever the value is equal to X push the corresponding index(1-based) into the vector vx.
- Now to answer each query check whether the size of vector vx is greater than or equal to query_value[i], if so print out the answer as vx[query_value[i]-1].
- If the size of vector vx is less than query_value[i], print answer as -1.

Entering edit mode

In the question it is mentioned that we are given an **integer in base 10**, which we first need to convert into **binary** and then **negate all the bits starting from the leftmost set bit**. This means that we need to **convert all 0 bits to 1 and all 1 bits to 0.** So, we can simply convert the integer into binary by using **repeated division by 2** and store the binary representation as a string. Then negate all bits and convert it back into base 10.

```
ll n;
cin > > n;
string s = "";
while(n!=0)
{
ll rem = n%2;
if(rem==0)
s+='0';
else
s+='1';
n/=2;
}
reverse(s.begin(), s.end());
ll len = s.length();
ll ans = 0;
for(ll i=0;i < len;i++)
{
ans*=2;
if(s[i]=='0')
ans+=1;
}
cout < < ans < < '\n';
```

Entering edit mode

Time complexity: O(1)

```
int n;
cin>>n;
int bits = (int)log2(n) +1; //number of bits in the given integer
// invert the number by taking xor of n and (2 raised to number of bits) - 1
int ans = (((1 < < bits ) - 1 ) ^ n ) ;
cout < < ans < < endl ;
```

Entering edit mode

First we mapped the indices of each number and checked if the given query number is less than equal to the number of indices of X then return the mp[X][query[i]-1] else -1 for the other case;

```
int n;
cin > > n ;
map < int , vector < int > > mp;
for( int i = 1 ; i < = n ; i++){
int x;
cin > > x;
mp[x].push_back(i);
}
int x;
cin > > x ;
auto v = mp[x];
int q;
cin > > q;
while(q--){
int num;
cin > > num;
if(num < = v.size()){
cout < < v[num-1] < < endl;
}else{
cout < < -1 < < endl;
}
}
```

Entering edit mode

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin>>n;
int i=0;
//Calculating number just greater than n in the power of two
while(pow(2,i)<n){
i++;
}
//Subtracting 1 to get all set bits
//Subtracting 'n' to get the answer after removing set bits in n
//Changing 1 to 0 and 0 to 1 (in short)
cout<<pow(2,i)-1-n<<endl;
return 0;
}
```