Question: Google Girl Hackathon 2023 OA question | Maximize Equal Numbers | XOR Distance
5
Entering edit mode

## Q1. Maximize Equal Numbers

You are given the following :

• An array a consisting of n elements
• Integer k

For each (1 ≤ i ≤ n ) perform the followingoperation exactly one time :

• Replace ai  by a+ x , where x ∈ [-k , k ] which denotes x should lie in the range of -k to k both inclusive

Determine the maximum length of subsequence of array a , such that all numbers in the subsequence are equal after applying the given operations

Notes

• A subsequence of array a is an array that can be derived from array a by removing some elements  from it (maybe none or all of them)
• Assuming 1 based indexing

Function description

Complete the MaximizeEqualNumbers functionprovided in the editor . This function takes 3 parameters and returns the maximum length of the subsequence

• n : Represents the size of array a
• k : Represents the integer k
• a : represents the array a of length n

Input format

Note: This is the input format that you must use to provide cuxtom input(available above the compile and test button)

• The first line contains an integer T denoting the number of test cases . T also denotes the number of times you have to run the MaximizetheequalNumbers function on a different set of inputs
• For each test case :
• first line contains two integers n and k
• the second line contains n space-sepparated integers denoting the elements of the array a

Output format

For each test case, print the maximum length of the susequence in new line .

The question has code snippets from CPP , Python , C and Java

Sample Input                   Sample Output
2                                            2
4 8                                         2
2 2 5 6
3 2
1 5 6

Explanation

The first line represents the number of test cases T=2

For test case 1:

Applying one operation with x= 0 on index 1,2,3 and 4 to get array a as [ 2, 2, 5, 6]

Therefore , the maximum length if the subsequence with equal numbers as a
2

For test case 2:
Applying one operation i with x = 0 on index 1 and 2 to get array a as [1,5,6]
Applying one operation on index 3 iwth x= 1 to get array a as [1,5,5]

Q2. XOR Distance

• You are given an array A of N coordinates in a 2D plane
• An integer K

Let the distance between two coordinates (x1,y1)  and (x2,y2) be (x1 ⊕ x2) +  (y1  y2) , where is bitwise exclusive OR

Determine the number of pairs (i,j) such that  i,j and the distance between coordinates at index i and j is K

Example

Assumption

• N = 3
• A = [(0,1),(2,3),(1,3)]
• K = 3

Approach

• Distance between coordinates (0,1) and (2,3) = (0 xor 2) + (1 xor 3) = 2+2=4

The question has code snippets from CPP , Python , C and Java

Sample Input                   Sample Output
1                                               4
4
0 0
0 1
0 0
1 0
1

Explanation

The first line contains the number of test cases  , T = 1

For the first test case

Given

• N = 4
• A = [(0,0), (0,1) ,(0,0) , (1,0)]
• K = 1

Approach

• Distance between coordinates (0, 1) and (1, 3) = (0 xor 1) + (1
xor 3) = 1 + 2 = 3
• Distance between coordinates (2,3) and (1, 3) = (2 xor 1) + (3 xor 3) = 3 + 0 = 3

There are 2 pairs of coordinates such that the distance between them is 3.

Function description
Complete the function solve provided in the editor. This function takes the following 3 parameters and returns

• N: Represents the number
• of coordinates in A
• A: Represents the coordinates in 2D plane
• K: Represents the integer K
• Input format

Note:
This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line containsdenoting the number of test

## Q2. XOR Distance

Entering edit mode
1

Can you provide constraints for the second question? on n and Ai

manish kumar patel
• 10
Entering edit mode
1

n<=105
x,y<=10and k<=102

sober
100
Entering edit mode
0

what is the constraint for 1st problem?

Gyan Prakash
• 0
5
Entering edit mode

## [P1] Maximize Equal Numbers

### Brief

Given N integers and an integer K, you are allowed to increase each integer by X, where X belongs to [-K, +K].
You want to make maximum numbers equal after modifying each of N numbers.

### Solution

ith number after modification will lie in range [Ai - K, Ai + K].
Thus, instead of viewing each number as a single point on number line, we can view it as a range.
Problem thus reduces to finding point on number line where maximum number of ranges overlap.

Example #1
A = [5, 7, 10, 8, 15]
K = 4

After modifying 5, it will be in range [1, 9]
After modifying 7, it will be in range [3, 11]
After modifying 10, it will be in range [6, 14], and so on..
This is represented by diagram below:-

Let Z be one of integers where maximum ranges overlap. For example above Z could be either of 8 or 9 where all 5 ranges overlap.
Thus, it is possible to convert all integers in array to either 8 or 9, that results in required answer as 5.

To verify, we can see adding +3 to 5, +1 to 7, -2 to 10, +0 to 8, and -4 to 12 results in array [8, 8, 8, 8, 8].

So how do we find this maximum overlapping ranges amongst given N ranges?

1. Simply insert into vector, for each range its starting and ending point along with flag whether they are starting or ending point.
For above example, this will result in {(S,1), (E, 9), (S, 3), (E, 11) .... (S, 8), (E, 16)}.
2. Sort this vector by integer in each pair inserted in vector.
3. Initialize variable current = 0
4. Now evaluate each pair in ascending order:-
1. increment current by 1when you encounter pair of type S (starting point), and
2. decrement current by 1 when you encounter pair of type E (ending point)
5. This essentially simulates us sweeping a line from left to right and counting current number of ranges overlapping!
6. Maximum value of variable currentis the required answer.

Code

``````int solve(vector<int> &A, int K) {
vector<pair<int,int>> sweep;
for (auto x: A) {
sweep.push_back({x-K, 0}); //0 -> flag for starting point
sweep.push_back({x+K, 1}); //1 -> flag for ending point
}
sort(sweep.begin(), sweep.end());
int ans = 0, current = 0;
for (auto x: sweep) {
if (x.second == 0) current++; else current--;
ans = max(ans, current);
}
return ans;
}
``````

Entering edit mode
1

Could you also post the solution to the 2nd question

sober
100
Entering edit mode
3

For 2nd question, this question based on trie + dfs + dp. So, first you have coordinates (x, y) take the bit representation of both x and y, and now take 4 posibilities of both x and y bits, i.e. for example if there is some bit in x at ith position is 0 and there is some bit in y at ith position is 1 you take it as (0, 1). so all the 4 posibilties are (0, 0), (0, 1), (1, 0), (1, 1). And now built a trie of every coordinate . then use dfs + dp to compute the count of all the pairs (i, j) such that  i < j, and there XOR distance is equal to k.

Mayank
• 90
Entering edit mode
0

I am not getting "now built a tree of every coordinate" , do you mean if there are N coordinates then we will build N tries, then how will use dfs,
It would be better if you provide code for the same

sober
100
Entering edit mode
0

Actually this is overkill for the problem. This problem is easy and can be solved without Trie / DP / DFS
Will post the solution when I get free.

slime
• 320
4
Entering edit mode

Here is solution for P2 as well on request by @Abhishek.

## [P2] XOR Distance

Let's use technique taught in class, solve 1D version of this problem and then extend its intuition to 2D.

### 1D SubProblem

`Given array of N integers, and an integer K, find number of ordered pairs whose XOR = K.`

To solve this, we need to understand that for any given integer say X, there exists a unique integer Y, such that X Y = K. (Think bit-by-bit and this will make sense).

Now, lets say for Ai, we want to find number of Aj such that Ai Aj = K for j < i.
This is easy, since Ai K will give you value of Aj !! All you need to check is how many Aj exists whose value is Ai
K. (This you can use unordered_map to keep track of).

Thus you can solve this problem in O(N).

### Original 2D Problem

Extending intuition, we can find out for (Xi, Yi) how many (Xj, Yj) exists for j < i whose XOR is K. How?
Lets say for some integers m and n, Xi m + Yi n = K is true. What all can be m, n?

It can be one of following K+1 cases:-
Case #1 : Xi ⊕ m = 0 and Yi ⊕ n = K. (This uniquely determines n, m)
Case #2 : Xi ⊕ m = 1 and Yi ⊕ n = K-1. (This uniquely determines n, m)
Case #3 : Xi ⊕ m = 2 and Yi ⊕ n = K-2. (This uniquely determines n, m)
....
Case #K+1 : Xi ⊕ m = K and Yi ⊕ n = 0. (This uniquely determines n, m)

Thus, find all possible points that you have seen so far (again using unordered_map) where n, m has values as one of above cases.
K <= 100, N <= 105 in given question. So this makes our solution as O(K.N)

Entering edit mode
1

A little correction you are finding solutions for X^ m + X^ n = K which is wrong, instead it should be X^ m + Y^ n = K

lets say we fix, X^ m = 1 then Y^ n = k-1  => what if we directly count how many X^ X=1 in mapX then Y^ Y=1 in mapY then it will give wrong answer because there may be a case when Xjand Yjdo not belongs to same pair.

sober
100
Entering edit mode
1

I don't think it's wrong, I guess you are missing implementation detail: we are mantaining a unordered_map of pair of integers. so Xi and Yi if found a hit in map, then that pair shall exist. If I am getting you wrong, let me know through an example. @abhishek

slime
• 320
Entering edit mode
0

got the point bro, thanks

But I think the time complexity would be tight as 10 * log(105) since hashMap would also count logN because we can't use unordered_map here since we counting pairs.

sober
100
Entering edit mode
2

You can use unordered_map with pairs in constant time with custom hash function
Quite certain this should pass and is expected solution, otherwise author of problem wouldn't have kept K <= 100!
Thought about Trie solution by @Mayank, despite having merits in idea it is unfortunately incorrect.

slime
• 320
Entering edit mode
0

You are right, I made the typo, above is exactly what I wanted to write

1.4k
Entering edit mode
0

sober
100
1
Entering edit mode

Code for 2nd problem
XOR DISTANCE
credit : @slime

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

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

int main() {

#ifndef ONLINE_JUDGE
freopen("input1.txt", "r", stdin);
freopen("output1.txt", "w", stdout);
freopen("Error.txt", "w", stderr);
#endif

int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n;

vector<pair<int, int>>v(n);
for (int i = 0; i < n; i++) {
cin >> v[i].first >> v[i].second;
}
cin >> k;

int ans = 0;
map<pair<int, int>, int>mp;
for (auto it : v) {

int x = it.first;
int y = it.second;

for (int j = 0; j <= k; j++) {

int a = j;   // a = x1 ^ x2
int b = k - a; // b = y1 ^ y2

//extracting x2,y2
int x2 = a ^ x;
int y2 = b ^ y;

if (mp.find({x2, y2}) != mp.end()) {
ans += mp[ {x2, y2}];
}
}

mp[ {x, y}]++;
}

cout << ans << endl;

}
return 0;
}
``````

Entering edit mode
1

Neatly implemented!

I have modified your code to remove extra O(log N) factor by replacing it with unordered_map with custom hash function.

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

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

//to hash any given pair
struct hash_pair {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
return hash1 ^ hash2;
}
};

int main() {

#ifndef ONLINE_JUDGE
freopen("input1.txt", "r", stdin);
freopen("output1.txt", "w", stdout);
freopen("Error.txt", "w", stderr);
#endif

int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n;

vector<pair<int, int>>v(n);
for (int i = 0; i < n; i++) {
cin >> v[i].first >> v[i].second;
}
cin >> k;

int ans = 0;
//map<pair<int, int>, int>mp;
unordered_map<pair<int,int>, int, hash_pair> mp;

for (auto it : v) {

int x = it.first;
int y = it.second;

for (int j = 0; j <= k; j++) {

int a = j;   // a = x1 ^ x2
int b = k - a; // b = y1 ^ y2

//extracting x2,y2
int x2 = a ^ x;
int y2 = b ^ y;

if (mp.find({x2, y2}) != mp.end()) {
ans += mp[ {x2, y2}];
}
}

mp[ {x, y}]++;
}

cout << ans << endl;

}
return 0;
}
``````

slime
• 320
Entering edit mode
1

Note
For this problem, since largest values is 109 we can actually use a collision-free hashing: mapping pair of integers into a single long long integer.

slime
• 320
Entering edit mode
0

Absolutely great idea!

sober
100
Entering edit mode
0

btw could we connect