16 days ago

John 690

Mumbai

Question 1

Ad Rotation

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

Question 2

K-th Occurrence Queries

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

2 days ago

Ujjwal Srivastava 280

Question 2

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.

6 months ago

Yash Sahijwani 770

Solution for Question 1

Analysis

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.

Implementation

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

10 months ago

eulersgamma • 50

Solution of Question 1

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 ;

10 months ago

eulersgamma • 50

Solution for Question 2

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

5 months ago

Siddhant Patil • 10

Solution for Question 1 : Ad Rotation

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

}