
إعطاء صفيف arr [] ل ن الأعداد الصحيحة المميزة و هدف القيمة المهمة هي التحقق مما إذا كان هناك زوج من العناصر في الصفيف الذي يساوي منتجه الهدف.
jsp javatpoint
أمثلة:
مدخل: arr [] = [1 5 7 -1 5] الهدف = 35
الإخراج: حقيقي
توضيح: كما 5* 7 = 35 الجواب صحيح.مدخل: arr [] = [-10 20 9 -40] الهدف = 30
الإخراج: خطأ شنيع
توضيح: لا يوجد زوج مع المنتج 30
جدول المحتوى
- [النهج الساذج] عن طريق توليد جميع الأزواج الممكنة - o (n^2) الوقت و o (1) الفضاء
- [نهج أفضل] باستخدام تقنية مؤشر - o (n log (n)) الوقت و o (1) الفضاء
- [النهج المتوقع] باستخدام Hashset - O (n) الوقت و o (n) الفضاء
[النهج الساذج] عن طريق توليد جميع الأزواج الممكنة - س (ن 2 ) الوقت و o (1) الفضاء
C++النهج الأساسي للغاية هو إنشاء جميع الأزواج الممكنة والتحقق مما إذا كان أي زوج موجودًا يكون منتجه يساوي القيمة المستهدفة ثم العودة حقيقي . إذا لم يكن هناك مثل هذا الزوج ، فأعود خطأ شنيع .
الحد الأدنى - الحد الأقصى
#include using namespace std; // Function to check if any pair exists whose product // equals the target bool isProduct(vector<int> &arr long long target) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (1LL * arr[i] * arr[j] == target) { return true; } } } return false; } int main() { vector<int> arr = {1 5 7 -1 5}; long long target = 35; cout << isProduct(arr target) << endl; return 0; }
C #include #include // Function to check if any pair exists whose product // equals the target bool isProduct(int arr[] int n long long target) { for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (1LL * arr[i] * arr[j] == target) { return true; } } } return false; } int main() { int arr[] = {1 5 7 -1 5}; long long target = 35; int n = sizeof(arr) / sizeof(arr[0]); printf('%dn' isProduct(arr n target)); return 0; }
Java class GfG { // Function to check if any pair exists whose product // equals the target static boolean isProduct(int[] arr long target) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if ((long) arr[i] * arr[j] == target) { return true; } } } return false; } public static void main(String[] args) { int[] arr = {1 5 7 -1 5}; long target = 35; System.out.println(isProduct(arr target)); } }
Python # Function to check if any pair exists whose product # equals the target def is_product(arr target): n = len(arr) for i in range(n - 1): for j in range(i + 1 n): if arr[i] * arr[j] == target: return True return False arr = [1 5 7 -1 5] target = 35 print(is_product(arr target))
C# using System; class GfG { // Function to check if any pair exists whose product // equals the target static bool IsProduct(int[] arr long target) { int n = arr.Length; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if ((long)arr[i] * arr[j] == target) { return true; } } } return false; } static void Main() { int[] arr = { 1 5 7 -1 5 }; long target = 35; Console.WriteLine(IsProduct(arr target)); } }
JavaScript // Function to check if any pair exists whose product // equals the target function isProduct(arr target) { let n = arr.length; for (let i = 0; i < n - 1; i++) { for (let j = i + 1; j < n; j++) { if (arr[i] * arr[j] === target) { return true; } } } return false; } let arr = [1 5 7 -1 5]; let target = 35; console.log(isProduct(arr target));
الإخراج
1
تعقيد الوقت: o (n²) لاستخدام حلقتين متداخلتين
المساحة المساعدة: س (1)
ما هو المتكلم
[نهج أفضل] باستخدام تقنية مؤشر - o (n log (n)) الوقت و o (1) الفضاء
C++يمكننا استخدام تقنية مؤشرتين لهذه المشكلة أيضًا ، ولكنها تنطبق فقط على البيانات التي يتم فرزها. لذا قم أولاً بفرز المصفوفة واحتفظ مؤشرين مؤشر واحد في البداية ( غادر ) وآخر في النهاية ( يمين ) من الصفيف. ثم تحقق من منتج العناصر في هذين المؤشرين:
- إذا كان المنتج يساوي هدف لقد وجدنا الزوج.
- إذا كان المنتج أقل من هدف حرك غادر مؤشر إلى يمين لزيادة المنتج.
- إذا كان المنتج أكبر من هدف حرك يمين مؤشر إلى غادر لتقليل المنتج.
#include using namespace std; // Function to check if any pair exists whose product equals the target. bool isProduct(vector<int> &arr long long target) { // Sort the array sort(arr.begin() arr.end()); int left = 0 right = arr.size() - 1; while (left < right) { // Calculate the current product long long currProd = 1LL*arr[left]*arr[right]; // If the product matches the target return true. if (currProd == target) return true; // Move the pointers based on comparison with target. if (currProd > target) right--; else left++; } return false; } int main() { vector<int> arr = {1 5 7 -1 5}; long long target = 35; cout << isProduct(arr target) << endl; return 0; }
C #include #include #include // Function to compare two integers (used in qsort) int compare(const void *a const void *b) { return (*(int *)a - *(int *)b); } // Function to check if any pair exists whose product // equals the target. bool isProduct(int arr[] int n long long target) { // Sort the array qsort(arr n sizeof(int) compare); int left = 0 right = n - 1; while (left < right) { // Calculate the current product long long currProd = (long long)arr[left] * arr[right]; // If the product matches the target return true. if (currProd == target) return true; // Move the pointers based on comparison with target. if (currProd > target) right--; else left++; } return false; } int main() { int arr[] = {1 5 7 -1 5}; long long target = 35; int n = sizeof(arr) / sizeof(arr[0]); printf('%dn' isProduct(arr n target)); return 0; }
Java import java.util.Arrays; class GfG { // Function to check if any pair exists whose product equals the target. static boolean isProduct(int[] arr long target) { // Sort the array Arrays.sort(arr); int left = 0 right = arr.length - 1; while (left < right) { // Calculate the current product long currProd = (long) arr[left] * arr[right]; // If the product matches the target return true. if (currProd == target) return true; // Move the pointers based on comparison with target. if (currProd > target) right--; else left++; } return false; } public static void main(String[] args) { int[] arr = {1 5 7 -1 5}; long target = 35; System.out.println(isProduct(arr target)); } }
Python # Function to check if any pair exists whose product equals the target. def isProduct(arr target): # Sort the array arr.sort() left right = 0 len(arr) - 1 while left < right: # Calculate the current product currProd = arr[left] * arr[right] # If the product matches the target return True. if currProd == target: return True # Move the pointers based on comparison with target. if currProd > target: right -= 1 else: left += 1 return False if __name__ == '__main__': arr = [1 5 7 -1 5] target = 35 print(isProduct(arr target))
C# using System; using System.Linq; class GfG { // Function to check if any pair exists whose product // equals the target. static bool isProduct(int[] arr long target) { // Sort the array Array.Sort(arr); int left = 0 right = arr.Length - 1; while (left < right) { // Calculate the current product long currProd = (long) arr[left] * arr[right]; // If the product matches the target return true. if (currProd == target) return true; // Move the pointers based on comparison with target. if (currProd > target) right--; else left++; } return false; } static void Main(string[] args) { int[] arr = { 1 5 7 -1 5 }; long target = 35; Console.WriteLine(isProduct(arr target)); } }
JavaScript // Function to check if any pair exists whose product // equals the target. function isProduct(arr target) { // Sort the array arr.sort((a b) => a - b); let left = 0 right = arr.length - 1; while (left < right) { // Calculate the current product let currProd = arr[left] * arr[right]; // If the product matches the target return true. if (currProd === target) return true; // Move the pointers based on comparison with target. if (currProd > target) right--; else left++; } return false; } let arr = [1 5 7 -1 5]; let target = 35; console.log(isProduct(arr target));
الإخراج
1
تعقيد الوقت: o (n log (n)) لفرز الصفيف
المساحة المساعدة: س (1)
[النهج المتوقع] باستخدام Hashset - O (n) الوقت و o (n) الفضاء
C++يمكننا استخدام أ مجموعة التجزئة للبحث بكفاءة. ونحن نتكرر من خلال الصفيف ، نتحقق مما إذا كان كل رقم عامل الهدف. إذا كان الأمر كذلك ، فنحن نرى ما إذا كان عامله المقابل بالفعل في المجموعة. إذا كان الأمر كذلك ، فسنعود حقيقي ؛ وإلا فإننا نضيف الرقم الحالي إلى المجموعة ونستمر.
#include #include #include using namespace std; // Function to check if any pair exists whose product // equals the target. bool isProduct(vector<int> &arr long long target) { // Use an unordered set to store previously seen numbers. unordered_set<int> st; for (int num : arr) { // If target is 0 and current number is 0 return true. if (target == 0 && num == 0) return true; // Check if current number can be a factor of the target. if (target % num == 0) { int secondNum = target / num; // If the secondNum has been seen before return true. if (st.find(secondNum) != st.end()) { return true; } // Mark the current number as seen. st.insert(num); } } return false; } int main() { vector<int> arr = {1 5 7 -1 5}; long long target = 35; cout << isProduct(arr target) << endl; return 0; }
Java import java.util.HashSet; class GfG { // Function to check if any pair exists whose product // equals the target. static boolean isProduct(int[] arr long target) { // Use a hash set to store previously seen numbers. HashSet<Integer> set = new HashSet<>(); for (int num : arr) { // If target is 0 and current number is 0 // return true. if (target == 0 && num == 0) return true; // Check if current number can be a factor of // the target. if (target % num == 0) { int secondNum = (int)(target / num); // If the secondNum has been seen before // return true. if (set.contains(secondNum)) return true; // Mark the current number as seen. set.add(num); } } return false; } public static void main(String[] args) { int[] arr = { 1 5 7 -1 5 }; long target = 35; System.out.println(isProduct(arr target)); } }
Python # Function to check if any pair exists whose product equals the target. def isProduct(arr target): # Use a set to store previously seen numbers. st = set() for num in arr: # If target is 0 and current number is 0 return True. if target == 0 and num == 0: return True # Check if current number can be a factor of the target. if target % num == 0: secondNum = target // num # If the secondNum has been seen before return True. if secondNum in st: return True # Mark the current number as seen. st.add(num) return False if __name__ == '__main__': arr = [1 5 7 -1 5] target = 35 print(isProduct(arr target))
C# using System; using System.Collections.Generic; class GfG { // Function to check if any pair exists whose product // equals the target. static bool isProduct(int[] arr long target) { // Use a hash set to store previously seen numbers. HashSet<int> set = new HashSet<int>(); foreach(int num in arr) { // If target is 0 and current number is 0 // return true. if (target == 0 && num == 0) return true; // Check if current number can be a factor of // the target. if (target % num == 0) { int secondNum = (int)(target / num); // If the secondNum has been seen before // return true. if (set.Contains(secondNum)) return true; // Mark the current number as seen. set.Add(num); } } return false; } static void Main(string[] args) { int[] arr = { 1 5 7 -1 5 }; long target = 35; Console.WriteLine(isProduct(arr target)); } }
JavaScript // Function to check if any pair exists whose product equals // the target. function isProduct(arr target) { // Use a set to store previously seen numbers. let seen = new Set(); for (let num of arr) { // If target is 0 and current number is 0 return // true. if (target === 0 && num === 0) return true; // Check if current number can be a factor of the // target. if (target % num === 0) { let secondNum = target / num; // If the secondNum has been seen before return // true. if (seen.has(secondNum)) return true; // Mark the current number as seen. seen.add(num); } } return false; } let arr = [ 1 5 7 -1 5 ]; let target = 35; console.log(isProduct(arr target));
الإخراج
1
تعقيد الوقت: س (ن) للتكرار الوحيد
المساحة المساعدة: o (n) لتخزين العناصر في مجموعة التجزئة