अनुक्रम Leetcode समाधान से अंकगणितीय प्रगति कर सकते हैं


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना
ऐरे छंटाई

समस्या का विवरण

समस्या में "अनुक्रम से अंकगणितीय प्रगति कर सकते हैं" हमें एक सरणी दी गई है, अब हमें जवाब देना होगा कि क्या यह संभव है कि अंकगणितीय प्रगति अनुक्रम को पुन: व्यवस्थित करके।

उदाहरण

arr = [3,1,5]
true

स्पष्टीकरण: हम सरणी को {1,3,5} के रूप में पुनर्व्यवस्थित कर सकते हैं जो 2 के रूप में एक सामान्य अंतर के साथ एक अंकगणितीय प्रगति बनाता है, इसलिए आउटपुट सही है।

अनुक्रम Leetcode समाधान से अंकगणितीय प्रगति कर सकते हैं के लिए दृष्टिकोण

एक अंकगणितीय श्रृंखला एक श्रृंखला है जिसमें आसन्न संख्या के बीच अंतर स्थिर होता है। सरणी को सॉर्ट करने और आसन्न तत्वों के बीच अंतर की जांच करने के लिए एक बहुत ही मूल दृष्टिकोण होगा, यदि अंतर सभी लगातार जोड़े के लिए समान है तो यह एक अंकगणितीय प्रगति है अन्यथा यह एक अंकगणितीय प्रगति नहीं है।

अनुक्रम Leetcode समाधान से अंकगणितीय प्रगति कर सकते हैं

छँटाई के लिए समय जटिलता nlogn है। हम सरणी के लिए एक लुकअप तालिका बनाकर समय की जटिलता में सुधार कर सकते हैं।

AP का nth शब्द = a + (n-1) * d है, जहाँ a श्रृंखला का पहला तत्व है, n तत्वों की संख्या है और d एक सामान्य अंतर है।

AP का न्यूनतम तत्व = a है

AP का अधिकतम तत्व = a + (n-1) * d है

d = (अधिकतम-न्यूनतम) / (एन -1)।

  1. हम सरणी के न्यूनतम और अधिकतम तत्व पाएंगे। इसका उपयोग करके हम d (सामान्य अंतर) की गणना कर सकते हैं।
  2. सरणी के लिए एक लुकअप तालिका बनाएं।
  3. अब हम पहले तत्व और सामान्य अंतर को जानते हैं।
  4. हम जाँचेंगे कि क्या a और d द्वारा गठित अंकगणितीय श्रृंखला के सभी n तत्व लुकअप टेबल में मौजूद हैं।
  5. यदि सभी तत्व लुकअप टेबल में मौजूद हैं तो हम अंक से अंकगणितीय प्रगति कर सकते हैं और हम अनुक्रम से अंकगणितीय प्रगति नहीं कर सकते हैं।

कार्यान्वयन

सी ++ कोड अनुक्रम से अंकगणितीय प्रगति कर सकता है

#include <bits/stdc++.h> 
using namespace std; 
  bool canMakeArithmeticProgression(vector<int>& arr) {
  unordered_set<int> seen;
  int mi = INT_MAX, mx = INT_MIN, n = arr.size();
        for (int a : arr) {
            mi = min(mi, a);
            mx = max(mx, a);
            seen.insert(a);
        }
        int diff = mx - mi;
        if (diff % (n - 1) != 0) {
            return false;
        }
        diff /= n - 1;
        while (--n > 0) {
            if (seen.find(mi)==seen.end()) {
                return false;
            }
            mi += diff;
        }
        return true;
    }
int main() 
{ 
 vector<int> arr = {3,5,1}; 
 cout <<boolalpha;   
 cout<<canMakeArithmeticProgression(arr)<<endl; 
 return 0;
}
true

अनुक्रम से अंकगणित प्रगति कर सकते हैं के लिए जावा कोड

import java.util.*; 
public class Tutorialcup {
 public static boolean canMakeArithmeticProgression(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        int mi = Integer.MAX_VALUE, mx = Integer.MIN_VALUE, n = arr.length;
        for (int a : arr) {
            mi = Math.min(mi, a);
            mx = Math.max(mx, a);
            seen.add(a);
        }
        int diff = mx - mi;
        if (diff % (n - 1) != 0) {
            return false;
        }
        diff /= n - 1;
        while (--n > 0) {
            if (!seen.contains(mi)) {
                return false;
            }
            mi += diff;
        }
        return true;
    }
  public static void main(String[] args) {
    int [] arr = {3,5,1}; 
    System.out.println( canMakeArithmeticProgression(arr));
  }
}
true

अनुक्रम लेटेकोड समाधान से अंकगणितीय प्रगति कर सकते हैं की जटिलता विश्लेषण

समय की जटिलता

उपरोक्त कोड की समय जटिलता है पर) क्योंकि हम लुकअप टेबल बनाने के लिए एरे को ट्रेस कर रहे हैं और अगर अंकगणित श्रृंखला के सभी तत्व लुकअप टेबल में मौजूद हैं। यहाँ n इनपुट सरणी का आकार है।

अंतरिक्ष की जटिलता

उपरोक्त कोड की अंतरिक्ष जटिलता है पर) क्योंकि हम सरणी के लिए एक लुकअप तालिका बना रहे हैं। यहाँ n इनपुट सरणी का आकार है।

संदर्भ