સિક્વન્સ લિટકોડ સોલ્યુશનથી અંકગણિત પ્રગતિ કરી શકે છે


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન
અરે સોર્ટિંગ

સમસ્યા નિવેદન

સમસ્યામાં "સિક્વન્સથી અંકગણિત પ્રગતિ કરી શકે છે" અમને એરે આપવામાં આવે છે, હવે અમારે જવાબ આપવાની જરૂર છે કે જો પેદા કરવાનું શક્ય છે તો અંકગણિત પ્રગતિ ક્રમ ફરીથી ગોઠવીને.

ઉદાહરણ

arr = [3,1,5]
true

સમજૂતી: આપણે એરેને {1,3,5 as તરીકે ફરીથી ગોઠવી શકીએ છીએ, જે 2 ની જેમ સામાન્ય તફાવત સાથે અંકગણિત પ્રગતિ બનાવે છે, તેથી આઉટપુટ સાચું છે.

સિક્વન્સ લિટકોડ સોલ્યુશનથી અંકગણિત પ્રગતિ માટેના અભિગમ

અંકગણિત શ્રેણી એ એક શ્રેણી છે જેમાં સંલગ્ન સંખ્યા વચ્ચેનો તફાવત સતત છે. એરેને સ sortર્ટ કરવા અને અડીને તત્વો વચ્ચેના તફાવતને તપાસો એ એક ખૂબ જ મૂળ અભિગમ હશે, જો તફાવત બધા સતત જોડી માટે સમાન હોય તો તે અંકગણિત પ્રગતિ છે અન્યથા તે અંકગણિત પ્રગતિ નથી.

સિક્વન્સ લિટકોડ સોલ્યુશનથી અંકગણિત પ્રગતિ કરી શકે છે

સ sortર્ટ કરવા માટેની સમયની જટિલતા એ અવ્યવસ્થિત છે. આપણે એરે માટે લુકઅપ ટેબલ બનાવીને સમયની જટિલતાને સુધારી શકીએ છીએ.

એપીનો નવમો પદ એ = એ + (એન -1) * ડી છે, જ્યાં એ શ્રેણીનો પ્રથમ તત્વ છે, એન તત્વોની સંખ્યા છે અને ડી એ સામાન્ય તફાવત છે.

એપીનું લઘુતમ તત્વ = = એ અને છે

એપીનું મહત્તમ તત્વ = એ + (એન -1) * ડી છે

ડી = (મહત્તમ-ન્યૂનતમ) / (એન -1).

  1. આપણે એરેના ન્યૂનતમ અને મહત્તમ તત્વો શોધીશું. તેનો ઉપયોગ કરીને આપણે ડી (સામાન્ય તફાવત) ની ગણતરી કરી શકીએ છીએ.
  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

જટિલતા વિશ્લેષણ સિક્વન્સ લિટકોડ સોલ્યુશનથી અંકગણિત પ્રગતિ કરી શકે છે

સમયની જટિલતા

ઉપરોક્ત કોડની સમય જટિલતા છે ઓ (એન) કારણ કે આપણે લુકઅપ ટેબલ બનાવવા માટે એરેને ટ્રversસ કરી રહ્યા છીએ અને તપાસ કરી રહ્યા છીએ કે લૂકઅપ ટેબલમાં અંકગણિત શ્રેણીના બધા ઘટકો હાજર છે કે નહીં. અહીં n એ ઇનપુટ એરેનું કદ છે.

જગ્યાની જટિલતા

ઉપરોક્ત કોડની અવકાશ જટિલતા છે ઓ (એન) કારણ કે આપણે એરે માટે લુકઅપ ટેબલ બનાવી રહ્યા છીએ. અહીં n એ ઇનપુટ એરેનું કદ છે.

સંદર્ભ