સ triર્ટ થયેલ એરેમાં તમામ ટ્રિપ્લેટ્સ છાપો જે એપી બનાવે છે


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એક્સેન્ચર ભેગા કેડન્સ ભારત Google માહિતી એડજ વધુ વધુ Pinterest
અરે હેશ શોધી રહ્યું છે

સમસ્યા "સ formર્ટ કરેલા એરેમાં તમામ ટ્રિપ્લેટ્સ છાપો જે એપી બનાવે છે" જણાવે છે કે અમે સ givenર્ટ કરેલ છે પૂર્ણાંક એરે. કાર્ય એ છે કે બધી સંભવિત ત્રિપુટીઓ શોધવા કે જે અંકગણિત પ્રગતિ રચી શકે.

સ triર્ટ થયેલ એરેમાં તમામ ટ્રિપ્લેટ્સ છાપો જે એપી બનાવે છે

ઉદાહરણ

arr[] = {1,3,5,7,8,12,15,16,20,30}
(1, 3, 5), (3, 5, 7), (1, 8, 15), (8, 12, 16), (12, 16, 20)

સમજૂતી

આ બધા એ ત્રિવિધિઓ છે જે એપી બનાવે છે

arr[] = {2,4,5,6,9,14,18,24}
(2, 4, 6), (4, 5, 6), (4, 9, 14), (4, 14, 24)

સમજૂતી

આ બધા એ ત્રિવિધિઓ છે જે એપી બનાવે છે

અલ્ગોરિધમ

  1. માંથી લૂપ i = 1 થી n-1(સમાવેલ નથી).
  2. J ની કિંમત i કરતા ઓછી અને k ની વેલ્યુ i કરતાં વધુ સેટ કરો.
  3. જ્યારે j> = 0 && કે <એન.
    1. તપાસો કે બે વર્તમાન એરે તત્વોનો સરવાળો અન્ય એરે તત્વની બરાબર છે કે નહીં,
      1. જો સાચું હોય, તો વર્તમાન ત્રણ તત્વો છાપો અને અનુક્રમે કે અને જેનું મૂલ્ય ઘટશે અને વધારશે.
    2. તપાસો કે જો બે તત્વોનો સરવાળો અન્ય તત્વ કરતાં બે વાર ઓછો છે, તો પછી, 1 ને XNUMX દ્વારા વધારો.
    3. તપાસો કે જો બે તત્વોનો સરવાળો અન્ય તત્વ કરતાં બે વાર વધારે હોય, તો પછી, j દ્વારા 1 ઘટાડો.

સમજૂતી

અમે આપી છે એ સortedર્ટ થયેલ એરે. અમને તમામ ત્રિપાઇઓ શોધવા માટે કહેવામાં આવ્યું છે જે અંકગણિત પ્રગતિ રચી શકે છે. એક અંકગણિત પ્રગતિને સંખ્યા ક્રમ તરીકે વ્યાખ્યાયિત કરી શકાય છે જેમાં તમામ તત્વો સંપૂર્ણ ક્રમ સાથે તેમની વચ્ચેના ચોક્કસ અંતર સાથે સતત આવે છે. આપણે એપીના ફોર્મ્યુલા દ્વારા ત્રિપુટી શોધીશું જેમાં એક + c = 2 બી જણાવે છે કે જો બે નંબરોનો સરવાળો ત્રીજી સંખ્યાની બમણી બરાબર હોય તો.

લૂપ માટે એક સાથે સંપૂર્ણ એરેને પસાર કરો અને એ જ્યારે લૂપ, 'જ્યારે લૂપ' એ તપાસવા જઈ રહ્યું છે કે આપણે શોધી કા .ીએ કે એલિમેન્ટ્સમાંથી ત્રણ એપી બનાવી શકે છે કે નહીં. જ્યારે પણ આપણે ફોર લૂપમાંથી પસાર થઈશું ત્યારે, આપણે j ની વેલ્યુ i ની વેલ્યુ કરતા ઓછી અને k ની વેલ્યુને i ની વેલ્યુ કરતા વધુ એક સેટ કરીશું. તે તપાસવા માટે અમારા માટે એક તત્વ પસંદ કરશે, તેથી જ્યારે પણ દરેક વખતે અમારી પાસે એરર [i], એરર [j], અને એઆર [કે] ની તપાસ કરવા માટે ત્રણ તત્વો હોય, ત્યારે દરેક, i, j અને k ની કિંમત અલગ અલગ હોય છે. લૂપ માટે હોય કે અંદર જ્યારે લૂપ.

જો આપણે જોયું કે બે તત્વોનો સરવાળો ત્રીજા તત્વની બરાબર છે, તો અમે તે ત્રણ એરે તત્વો છાપવા જઈ રહ્યા છીએ, તેઓ એક એપી બનાવી શકે છે. આપણે આપણા અલ્ગોરિધમ પ્રમાણે j અને k ની વેલ્યુ અપડેટ કરીશું. જો અમને બે તત્વોનો સરવાળો તૃતીય તત્વ કરતાં બમણાથી ઓછો મળ્યો. આપણે k ની વેલ્યુમાં વધારો કરીશું, અથવા જો આપણને ત્રીજા તત્વ કરતાં બે વાર વધારે મળ્યું હોય, તો આપણે j ની કિંમત ઘટાડીશું. જ્યાં સુધી અમે આખા એરેને પસાર ન કરીએ અને એપી બનાવી શકે તેવા બધા સંભવિત તત્વો શોધી ન લે ત્યાં સુધી આ ચાલુ રહેશે.

કોડ

સ +ર્ટ કરેલા એરેમાં તમામ ટ્રિપ્લેટ્સને છાપવા માટે સી ++ કોડ જે એપી બનાવે છે

#include<iostream>

using namespace std;

void getTripletsWithAP(int arr[], int n)
{
  for (int i = 1; i < n - 1; i++)
  {
    int j = i - 1, k = i + 1;
        while(j >= 0 && k < n)
        {
            if (arr[j] + arr[k] == 2 * arr[i])
            {
        cout <<arr[j]<< " "<<arr[i]<<" "<<arr[k]<< endl;
                k++;
                j--;
            }
            else if (arr[j] + arr[k] < 2 * arr[i])
                k++;
            else
                j--;
        }
  }
}
int main()
{
  int arr[] = {1,3,5,7,8,12,15,16,20,30};
  int n = sizeof(arr) / sizeof(arr[0]);
  getTripletsWithAP(arr, n);
  return 0;
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

સ formર્ટ કરેલા એરેમાં તમામ ટ્રિપ્લેટ્સને છાપવા માટે જાવા કોડ જે એપી બનાવે છે

class TripletAP
{
    public static void getTripletsWithAP(int arr[], int n)
    {
        for (int i = 1; i < n - 1; i++)
        {
            int j = i - 1, k = i + 1;
            while(j >= 0 && k < n)
            {
                if (arr[j] + arr[k] == 2 * arr[i])
                {
                    System.out.println(arr[j] +" " +arr[i]+ " " + arr[k]);
                    k++;
                    j--;
                }
                else if (arr[j] + arr[k] < 2 * arr[i])
                    k++;
                else
                    j--;
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {1,3,5,7,8,12,15,16,20,30};
        int n = arr.length;
        getTripletsWithAP(arr, n);
    }
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન2જ્યાં “એન”  એરેમાં તત્વોની સંખ્યા છે. કારણ કે આપણી પાસે બે નેસ્ડ લૂપ છે જ્યાં પ્રથમ લૂપ ચાલે છે ત્યાં સુધી આપણે અંત સુધી પહોંચતા નથી અને ત્યારબાદ બીજા નેસ્ડ લૂપનો ઉપયોગ એપીના તત્વો શોધવા માટે થાય છે.

અવકાશ જટિલતા

ઓ (1) કોઈ વધારાની જગ્યા જરૂરી નથી.