Given two arrays A[] and B[] of length N and M respectively and a prime number X, the task is to find the number of ordered pair of indices (i, j) that satisfies the following conditions:
- 1 ? i ? N and 1 ? j ? M
- ( Ai ? Bj ) < X
- (( Ai ? ( Ai ? Bj )) ? 1) % X = 0
Note: ? is XOR operator.
Examples:
Input: A[] = {7, 14} , B = {2, 13}, X = 17
Output: 1
Explanation: There are 4 ordered pairs of indices. Looking at them individually,
(1, 1) satisfies because (7 ? 2) = 5 < 17, and ((7? (7 ? 2)) ? 1) = 34 is divisible by 17.
(1, 2) satisfies because (7 (7 ? 13)) ? 1) = 69 is not divisible by 17.
(2, 1) satisfies because ((14?(14 ? 2)) ? 1) = 167 is not divisible by 17
(2, 2) satisfies because ((14?(14 ? 13)) ? 1) = 41 is not divisible by 17.Input: A[] = {3} , B = {3}, X = 11
Output: 0
Approach: The problem can be solved based on the following mathematical observation:
Consider two values Ai and Bj which satisfies the condition.
So, ( Ai?( Ai ? Bj )?1) mod X = 0
(( Ai?( Ai ? Bj )) mod X = 1
( Ai ? Bj ) mod X = Ai?1 mod X
( Ai ? Bj )= Ai?1 mod X (according to the last condition)
Bj = ( Ai ? ( Ai-1 mod X ))So if the value of Ai is known we can easily check if there is any value in B[] that satisfies the condition.
Follow the below steps to implement the idea:
- Store all the elements of B[] in a map.
- Traverse through the array A[]:
- Note if the values A[i] and X are not prime then the condition cannot be satisfied, as we cannot get some multiple of A[i] which will give 1 as a remainder when divided by X.
- Otherwise, calculate the value from B that will satisfy the condition using the above formula.
- Find the count of that value and add that to the answer.
- Return the final value of the answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>#include <iostream>#include <map>using namespace std;// Function to return gcd of a and bint gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }int mI(int a, int m){ int m0 = m; int y = 0, x = 1; if (m == 1) return 0; while (a > 1) { int q = a / m; int t = m; m = a % m; a = t; t = y; y = x - q * y; x = t; } if (x < 0) x += m0; return x;}// Function to find number of pairsint findPairs(int a[], int b[], int n, int m, int p){ map<int, int> cnt; for (int j = 0; j < m; j++) { cnt[b[j]]++; } int ans = 0; for (int i = 0; i < n; i++) { if (gcd(a[i], p) != 1) { continue; } int x = mI(a[i], p) ^ a[i]; ans += cnt[x]; } return ans;}// Driver codeint main(){ int A[] = { 7, 14 }; int B[] = { 2, 13 }; int N = sizeof(A) / sizeof(A[0]); int M = sizeof(B) / sizeof(B[0]); int X = 17; // Function call cout << findPairs(A, B, N, M, X); return 0;}// This code is contributed by aarohirai2616. |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to find gcd of two number static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } static int mI(int a, int m) { int m0 = m; int y = 0, x = 1; if (m == 1) return 0; while (a > 1) { int q = a / m; int t = m; m = a % m; a = t; t = y; y = x - q * y; x = t; } if (x < 0) x += m0; return x; } // Function to find number of pairs public static int findPairs(int a[], int b[], int n, int m, int p) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < m; i++) { if (!map.containsKey(b[i])) map.put(b[i], 1); else map.put(b[i], map.get(b[i]) + 1); } int ans = 0; for (int i = 0; i < n; i++) { if (gcd(a[i], p) != 1) continue; int x = mI(a[i], p) ^ a[i]; if (!map.containsKey(x)) continue; ans = ans + map.get(x); } return ans; } // Driver Code public static void main(String[] args) { int A[] = { 7, 14 }; int B[] = { 2, 13 }; int N = A.length; int M = B.length; int X = 17; // Function call System.out.println(findPairs(A, B, N, M, X)); }} |
Python3
# Python3 code to implement the approach# Function to return gcd of a and bdef gcd(a, b) : if b == 0 : return a else : return gcd(b, a % b); def mI(a, m) : m0 = m; y = 0; x = 1; if (m == 1) : return 0; while (a > 1) : q = a // m; t = m; m = a % m; a = t; t = y; y = x - q * y; x = t; if (x < 0) : x += m0; return x;# Function to find number of pairsdef findPairs(a, b, n, m, p) : cnt = dict.fromkeys(b, 0); for j in range(m) : cnt[b[j]] += 1; ans = 0; for i in range(n) : if (gcd(a[i], p) != 1) : continue; x = mI(a[i], p) ^ a[i]; if x in cnt: ans += cnt[x]; else : continue; return ans;# Driver codeif __name__ == "__main__" : A = [ 7, 14 ]; B = [ 2, 13 ]; N = len(A); M = len(B); X = 17; # Function call print(findPairs(A, B, N, M, X)); # This code is contributed by AnkThon |
C#
// Include namespace systemusing System;using System.Collections.Generic;using System.Collections;public class GFG{ // Function to find gcd of two number public static int gcd(int a, int b) { if (b == 0) { return a; } return GFG.gcd(b, a % b); } public static int mI(int a, int m) { var m0 = m; var y = 0; var x = 1; if (m == 1) { return 0; } while (a > 1) { var q = (int)(a / m); var t = m; m = a % m; a = t; t = y; y = x - q * y; x = t; } if (x < 0) { x += m0; } return x; } // Function to find number of pairs public static int findPairs(int[] a, int[] b, int n, int m, int p) { var map = new Dictionary<int, int>(); for (int i = 0; i < m; i++) { if (!map.ContainsKey(b[i])) { map[b[i]] = 1; } else { map[b[i]] = map[b[i]] + 1; } } var ans = 0; for (int i = 0; i < n; i++) { if (GFG.gcd(a[i], p) != 1) { continue; } var x = GFG.mI(a[i], p) ^ a[i]; if (!map.ContainsKey(x)) { continue; } ans = ans + map[x]; } return ans; } // Driver Code public static void Main(String[] args) { int[] A = {7, 14}; int[] B = {2, 13}; var N = A.Length; var M = B.Length; var X = 17; // Function call Console.WriteLine(GFG.findPairs(A, B, N, M, X)); }}// This code is contributed by aadityaburujwale. |
Javascript
// JavaScript code to implement the approach// Function to return gcd of a and bfunction gcd(a, b) { return b == 0 ? a : gcd(b, a % b);}function mI(a, m) { let m0 = m; let y = 0, x = 1; if (m == 1) return 0; while (a > 1) { let q = Math.floor(a / m); let t = m; m = a % m; a = t; t = y; y = x - q * y; x = t; } if (x < 0) x += m0; return Math.floor(x);}// Function to find number of pairsfunction findPairs(a, b, n, m, p) { let cnt = {}; for (let j = 0; j < m; j++) { if (cnt.hasOwnProperty(b[j])) cnt[b[j]]++; else cnt[b[j]] = 1; } let ans = 0; for (let i = 0; i < n; i++) { if (gcd(a[i], p) != 1) { continue; } let x = mI(a[i], p) ^ a[i]; if (cnt.hasOwnProperty(x)) ans += cnt[x]; } return ans;}// Driver codelet A = [7, 14];let B = [2, 13];let N = A.length;let M = B.length;let X = 17;// Function callconsole.log(findPairs(A, B, N, M, X));// This code is contributed by ishalkhandelwals. |
Output
1
Time Complexity: O(N * log X)
Auxiliary Space: O(m), space used by map.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
