14 months ago

PoGo 2.4k

Mumbai

Fractional Knapsack

Problem Description
You are inside Gringotts Gold Bank with a Knapsack that can hold B weight of Gold coins.
In the Gringotts bank, gold coins have some unique properties:
1. Each Gold coin has a weight equal to some non-negative power of 2.
2. Each Gold Coin can be further divided into two gold coins of equal weight.
There are N gold coins in the Bank, given by array A. where Ali] is the weight of the it gold coin.
You have to fill the knapsack completely, by making minimum number of divisions of the gold coins.
Calculate the minimum number of divisions needed to fill the knapsack completely.
Note: In case it is impossible to fill the knapsack completely, output -1.
Problem Constraints

1 <= N <= 10^5
1 <= B <= 10^18
1 <= A[i] <= 10^9

Input Format

The first argument given is an array. A
The second argument given is an integer, B.

Output Format

Return an integer denoting the minimum number of division that are required to fill the knapsack completely.
Example Input
Input 1:
A - [16, 1, 4, 1]
B = 23
Input 2:
A = [1, 32, 1]
B = 10

Output 1

-1

Output2

2

Example Explanation
Explanation 1:

It is impossible to fill the knapsack of weight 23

Explanation 2:
You can convert cold coin of weight 32 into gold coin of weight 8 with 2 divisions.
1.e. 32 -> 16 ÷ 16
16 -> 8 + 8.
And Now to fill the knapsack with weight 10
three gold coins with weight 1, 1

XOR subsequences

Problem Description

You are given an array A. you have to create an array & which is a subsequence of A
An array B is called valid if it satisfies both the conditions
B(i] « B[i+1] where 1<= i « (B).
2. bit count( B[1] * ....... * B[i-1] * B[i] ca bit_count|B(i+1]) where 1 ca i « B).
Let X be the Bitwise XOR of all the elements in valid array B
You need to find the number of different values of X that can be formed.
Note : bit_ countit) is the number of set bits present in the binary representation of t
Problem Constraints
1 <=  |A| <= 10^5
1 <=  A[i] <=  100

Scramble String

Given a string we may represent it as a binary tree by partioning  it to two non-empty substrings recursively . Below is one possible representation of A = "great"

To scramble the string, we may choose any non-leaf node and swap its two children For example, if we choose the node "gr" and swap its two children, it produces a scrambled
string "rgeat"

We say that "rgtae" is a scrambled string of "great' .Given two strings A and B of the same length, determine if B is a scrambled string of S
Input Format:
The first argument of input contains a string A
The second argument of input contains a string B
input contains a string l
Output Format:
Return an integer, 0 or 1
0 : False
1 : True
Constraints:
1 = len(A), len(8) <= 50
Examples:

Input

A = "we"

B= "we"
Output

1

Water Level

Problem Description
There is garden which contains N water fountains, each placed at distance 1 to N. Each water fountain
Every morning Q people come to Walk in garden. People are represented as follow.
Each people drink water from fountain numbered L to R and reduce their water level to maxin, Al) - K)
Assuming people come in serial order, find the count of fountains with zero total water level after each person.

Problem Constraints
1 <= N, Q <= 10⁵
1 <= A[i], K <= 10^9
• 1 <= L <=R<=N
Example Input

Input
15.
31.
[ [1, 2, 1)
12, 3, 1]
(1, 3, 411
Input 2:
[1, 1, 18])

Output 1

[0,0,2]

output 2

[1]

13 months ago

prateekin • 30

Hyderabad

Read Books Answer:

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

void f(vector<int> &A, vector<int> &B){
    vector<int> c(B.size(), -1);
    vector<int>preSum(A.size(), 0);
    preSum[0] = A[0];
    for(int i = 1; i < A.size(); i++){
        preSum[i] = preSum[i-1] + A[i];
    }
    for(int i = 0; i < B.size(); i++){
        int val = B[i];
        int x = val / preSum[A.size()-1];
        int y = val%preSum[A.size()-1];
        if (y == 0){
            c[i] = x*A.size();
            continue;
        }
        int cnt =0 ;
        for(int j = 0 ; j < A.size(); j++){
            if(A[j] >= y){
                cnt = j + 1;
                break;
            }
        }
        int res = (x*A.size()) + cnt; 
        if (res >  0){
            c[i] = res;
        }
    }

    for(auto x : c){
        cout << x <<" ";
    }
}

int main(){
    vector<int> A{7, -15, 19, -15, -11, 1, 17, 5, -18};
    vector<int> B{28, 22, 13, 27, 36, 48, 33, 47, 37};

    // vector<int> A{1};
    // vector<int> B{100};
    f(A, B);
    
}