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

Task

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

Task

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.
Thus, the answer Is 2.


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

  • 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

ADD COMMENTlink 10 months ago sober 100
Entering edit mode
1

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

 

ADD REPLYlink 13 months ago
manish kumar patel
• 10
Entering edit mode
1

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

 

ADD REPLYlink 13 months ago
sober
100
Entering edit mode
0

what is the constraint for 1st problem?

ADD REPLYlink 12 months ago
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;
}

 

ADD COMMENTlink 13 months ago slime • 320
Entering edit mode
1

Could you also post the solution to the 2nd question

ADD REPLYlink 13 months ago
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.

ADD REPLYlink 13 months ago
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

ADD REPLYlink 13 months ago
sober
100
Entering edit mode
0

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

ADD REPLYlink 13 months ago
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) 

 

 

 

 

ADD COMMENTlink 13 months ago slime • 320
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. 

 

ADD REPLYlink 13 months ago
sober
100
Entering edit mode
1

Have updated the typo, had written Xjinstead of Yi as you had pointed out.
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

ADD REPLYlink 13 months ago
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.
 

ADD REPLYlink 13 months ago
sober
100
Entering edit mode
2

You can use unordered_map with pairs in constant time with custom hash functionwink
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.

ADD REPLYlink 13 months ago
slime
• 320
Entering edit mode
0

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

ADD REPLYlink 13 months ago
admin
1.4k
Entering edit mode
0

Please read the full comment i made above.

ADD REPLYlink 13 months ago
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;
}


 

ADD COMMENTlink 13 months ago sober 100
Entering edit mode
1

Neatly implemented!yes

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

 

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

 

ADD REPLYlink 13 months ago
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.

ADD REPLYlink 13 months ago
slime
• 320
Entering edit mode
0

Absolutely great idea!

ADD REPLYlink 13 months ago
sober
100
Entering edit mode
0

btw could we connect

ADD REPLYlink 10 months ago
sober
100

Login before adding your answer.

APPLY NOWSimilar Posts
Loading Similar Posts