എല്ലാ പെട്രോൾ പമ്പുകളും സന്ദർശിക്കുന്ന ആദ്യത്തെ സർക്കുലർ ടൂർ കണ്ടെത്തുക


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഫാക്റ്റ്സെറ്റ് മൈക്രോസോഫ്റ്റ് മോർഗൻ സ്റ്റാൻലി Zoho
വരി

ഉള്ളടക്ക പട്ടിക

പ്രശ്നം പ്രസ്താവന

“എല്ലാ പെട്രോൾ പമ്പുകളും സന്ദർശിക്കുന്ന ആദ്യത്തെ സർക്കുലർ ടൂർ കണ്ടെത്തുക” എന്ന പ്രശ്നം ഒരു വൃത്താകൃതിയിലുള്ള റോഡിൽ എൻ പെട്രോൾ പമ്പുകളുണ്ടെന്ന് പറയുന്നു. ഓരോ പെട്രോൾ പമ്പിലും ഉള്ള പെട്രോളും രണ്ട് പെട്രോൾ പമ്പുകൾ തമ്മിലുള്ള ദൂരം നികത്താൻ ആവശ്യമായ പെട്രോളിന്റെ അളവും കണക്കിലെടുക്കുമ്പോൾ. അതിനാൽ ഒരു ട്രക്ക് ആരംഭിച്ച് സർക്കിൾ പൂർത്തിയാക്കാൻ കഴിയുന്ന ആദ്യത്തെ പെട്രോൾ പമ്പ് നിങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്.
ഇൻപുട്ട് ഫോർമാറ്റ്, {x, y as ആണ്, ഇവിടെ x എന്നത് പെട്രോൾ പമ്പിനുള്ള പെട്രോളും y ആണ് ഈ പെട്രോൾ പമ്പിൽ നിന്ന് അടുത്ത പെട്രോൾ പമ്പിലേക്ക് എത്താൻ ആവശ്യമായ ഇന്ധനവും.
സാധ്യമായ ടൂർ ഇല്ലെങ്കിൽ, output ട്ട്‌പുട്ട് -1.

ഉദാഹരണങ്ങൾ

{{5, 3}, {2, 7}, {11, 2}, {8, 9}}
3

 

എല്ലാ പെട്രോൾ പമ്പുകളും സന്ദർശിക്കുന്ന ആദ്യത്തെ സർക്കുലർ ടൂർ കണ്ടെത്തുക

 

{{1, 1}, {2, 2}, {1, 2}, {3, 1}}
4
{{2, 3}, {4, 5}, {1, 1}, {3, 3}}
-1

നിഷ്കളങ്കമായ സമീപനം

ഓരോ പെട്രോൾ പമ്പും ആരംഭ പോയിന്റായി ഓരോന്നായി കണക്കാക്കുന്നു. സാധുവായ ഒരു ടൂർ നിലവിലുണ്ടെങ്കിൽ. നിലവിലെ പെട്രോൾ പമ്പ് നമ്പർ നൽകുക. അല്ലെങ്കിൽ ഏതെങ്കിലും പെട്രോൾ പമ്പിൽ നിന്ന് ടൂർ സാധ്യമല്ലെങ്കിൽ -1 മടങ്ങുക.

  1. 1 മുതൽ n വരെ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക, ഈ ലൂപ്പ് ith പെട്രോൾ പമ്പിനെ ആരംഭ പോയിന്റായി കണക്കാക്കുന്നു.
  2. ട്രക്കിലെ പെട്രോളിന്റെ അളവിനെ പ്രതിനിധീകരിക്കുന്ന 0 എന്ന വേരിയബിൾ currFuel ആരംഭിക്കുക.
  3. Jth പെട്രോൾ പമ്പിൽ നിന്ന് (j + 1) th പെട്രോൾ പമ്പിലേക്ക് യാത്ര ചെയ്യാൻ, (ഇന്ധനം [j] - വില [j]) ഇന്ധനത്തിന്റെ അളവ് currFuel- ൽ ചേർക്കുന്നു.
  4. Ith പെട്രോൾ പമ്പിൽ നിന്ന് സർക്കിളിൽ മുന്നോട്ട് പോകാൻ ആരംഭിച്ച് ഓരോ ഘട്ടത്തിലും അധിക ഇന്ധനം (ഇന്ധനം [j] - ചെലവ് [j]) ചേർക്കുക, currFuel> = 0 ആയിരിക്കുമ്പോൾ ഈ പ്രക്രിയ ആവർത്തിക്കുക.
  5. എല്ലാ n പെട്രോൾ പമ്പുകളിലൂടെയും ട്രക്കിന് സഞ്ചരിക്കാൻ കഴിയുമെങ്കിൽ, ഞാൻ മടങ്ങുക. അല്ലെങ്കിൽ അടുത്ത i നായി തുടരുക.
  6. ട്രക്കിന് മുഴുവൻ സർക്കിളിലൂടെ സഞ്ചരിക്കാൻ i ഇല്ലെങ്കിൽ, -1 മടങ്ങുക.

കോഡ്

എല്ലാ പെട്രോൾ പമ്പുകളും സന്ദർശിക്കുന്ന ആദ്യത്തെ സർക്കുലർ ടൂർ കണ്ടെത്തുന്നതിനുള്ള ജാവ കോഡ്

class FindTheFirstCircularTourThatVisitsAllThePetrolPumps {
    private static int findPetrolPump(int[] fuel, int[] costs) {
        // Total number of petrol pumps
        int n = fuel.length;

        // one by one consider all the petrol pumps as starting point
        for (int i = 0; i < n; i++) {
            // initialize currPetrol as 0, it represents the amount of petrol in the truck
            int currPetrol = 0;
            // travelled represents the number of petrol pumps travelled by truck
            int travelled = 0;
            // while there is some petrol in the truck, travel to the next petrol pump
            while (currPetrol >= 0 && travelled < n) {
                // fuel added to the truck when it cross petrol pump
                // number j is (fuel[j] - cost[j])
                currPetrol += (fuel[(i + travelled) % n] - costs[(i + travelled) % n]);
                travelled++;
            }
            // if the truck has travelled all the petrol pumps
            // with some fuel left, return i
            if (travelled == n && currPetrol >= 0) {
                return (i + 1);
            }
        }
        
        // no possible way to travel the circle
        return -1;
    }

    public static void main(String[] args) {
        // Example 1
        int fuel1[] = new int[] {5, 2, 11, 8};
        int costs1[] = new int[] {3, 7, 2, 9};
        System.out.println(findPetrolPump(fuel1,costs1));

        // Example 2
        int fuel2[] = new int[] {1, 2, 1, 3};
        int costs2[] = new int[] {1, 2, 2, 1};
        System.out.println(findPetrolPump(fuel2, costs2));

        // Example 3
        int fuel3[] = new int[] {2, 4, 1, 3};
        int costs3[] = new int[] {3, 5, 1, 3};
        System.out.println(findPetrolPump(fuel3, costs3));
    }
}
3
4
-1

എല്ലാ പെട്രോൾ പമ്പുകളും സന്ദർശിക്കുന്ന ആദ്യത്തെ സർക്കുലർ ടൂർ കണ്ടെത്തുന്നതിനുള്ള സി ++ കോഡ്

#include <iostream>
using namespace std;

int findPetrolPump(int *fuel, int *costs, int n) {
    // one by one consider all the petrol pumps as starting point
    for (int i = 0; i < n; i++) {
        // initialize currPetrol as 0, it represents the amount of petrol in the truck
        int currPetrol = 0;
        // travelled represents the number of petrol pumps travelled by truck
        int travelled = 0;
        // while there is some petrol in the truck, travel to the next petrol pump
        while (currPetrol >= 0 && travelled < n) {
            // fuel added to the truck when it cross petrol pump
            // number j is (fuel[j] - cost[j])
            currPetrol += (fuel[(i + travelled) % n] - costs[(i + travelled) % n]); 
            travelled++;
        }
        // if the truck has travelled all the petrol pumps
        // with some fuel left, return i
        if (travelled == n && currPetrol >= 0) {
            return (i + 1);
        }
    }
    
    // no possible way to travel the circle
    return -1;
}

int main() {
  // Example 1
    int fuel1[] = {5, 2, 11, 8};
    int costs1[] = {3, 7, 2, 9};
    cout<<findPetrolPump(fuel1, costs1, sizeof(fuel1) / sizeof(fuel1[0]))<<endl;

    // Example 2
    int fuel2[] = {1, 2, 1, 3};
    int costs2[] = {1, 2, 2, 1};
    cout<<findPetrolPump(fuel2, costs2, sizeof(fuel2) / sizeof(fuel2[0]))<<endl;

    // Example 3
    int fuel3[] = {2, 4, 1, 3};
    int costs3[] = {3, 5, 1, 3};
    cout<<findPetrolPump(fuel3, costs3, sizeof(fuel3) / sizeof(fuel3[0]))<<endl;
  
  return 0;
}
3
4
-1

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n2), സമയ സങ്കീർണ്ണതയാണ്. നൽകിയിരിക്കുന്ന ഇൻപുട്ടിലെ പെട്രോൾ പമ്പുകളുടെ എണ്ണം N ആണ്. ഇവിടെ നമുക്ക് പോളിനോമിയൽ സങ്കീർണ്ണതയുണ്ട്, കാരണം ഓരോ പെട്രോൾ പമ്പും ആരംഭ പോയിന്റായി ഞങ്ങൾ കണക്കാക്കുന്നു. ഓരോ പെട്രോൾ പമ്പും ആരംഭിച്ചതിനുശേഷം ഞങ്ങൾ ഒരു പൂർണ്ണ ടൂർ നടത്തി. ടൂർ സമയത്ത് പെട്രോൾ ടാങ്ക് ശൂന്യമാണോയെന്ന് പരിശോധിച്ചു. അതിനാൽ ഞങ്ങൾക്ക് N ആരംഭ പോയിന്റുകളുണ്ടായിരുന്നു, തുടർന്ന് ഓരോ ആരംഭ പോയിന്റിലും കവർ ചെയ്യാൻ N-1 പെട്രോൾ പമ്പുകൾ ഉണ്ടായിരുന്നു. അങ്ങനെ സമയ സങ്കീർണ്ണത O (N ^ 2) ആണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), ഓരോ ഘടകത്തിനും ഒരേസമയം ആവശ്യമായ വിവരങ്ങളൊന്നും ഞങ്ങൾ ഇവിടെ സംരക്ഷിച്ചിട്ടില്ല. അതിനാൽ ഞങ്ങൾ കൂടുതൽ സ്ഥലം ഉപയോഗിച്ചിട്ടില്ല. സ്‌പേസ് സങ്കീർണ്ണതയെ സ്ഥിരമാക്കുന്ന വേരിയബിളുകളുടെ സ്ഥിരമായ എണ്ണം ഞങ്ങൾ ഉപയോഗിച്ചു.

ഒപ്റ്റിമൽ സമീപനം

ഈ പ്രശ്നം പരിഹരിക്കുക എന്നതാണ് ഏറ്റവും നല്ല ആശയം a വരി. ഒരു വേരിയബിൾ‌ കർ‌ഫ്യൂൾ‌ 0 ആയി ആരംഭിക്കുക. ഏത് നിമിഷവും currFuel നെഗറ്റീവ് ആകുകയാണെങ്കിൽ, currFuel നെഗറ്റീവ് ആകുന്നതുവരെ പെട്രോൾ പമ്പുകൾ ക്യൂവിൽ നിന്ന് ഓരോന്നായി പോപ്പ് out ട്ട് ചെയ്യുക. എല്ലാ n പെട്രോൾ പമ്പുകളും ക്യൂവിൽ ഉണ്ടെങ്കിൽ, ആരംഭ പോയിന്റ് നൽകുക, അല്ലാത്തപക്ഷം n പെട്രോൾ പമ്പുകൾ ക്യൂവിൽ നിൽക്കാൻ ഒരു വഴിയുമില്ലെങ്കിൽ, മടങ്ങുക -0.

നമ്മൾ ഇന്ധനത്തിലും കോസ്റ്റ് അറേയിലും ഒരു ക്യൂ രൂപപ്പെടുത്തിയാൽ ക്യൂ ഉപയോഗിക്കുന്ന ഇടം ലാഭിക്കാൻ കഴിയും. അറേകളിലെ ആരംഭ, അവസാന പോയിന്ററുകൾ ഉപയോഗിച്ച് ഇത് നേടാനാകും.

  1. ആരംഭം, അവസാനം, കർഫ്യൂവൽ എന്നിവ 0 ആയി സമാരംഭിക്കുക, ഇവിടെ ആരംഭം ട്രക്കിന്റെ ആരംഭ പോയിന്റിനെ പ്രതിനിധീകരിക്കുന്നു, അവസാനം സന്ദർശിക്കാനുള്ള അടുത്ത പെട്രോൾ പമ്പിനെയും പ്രതിനിധീകരിക്കുന്നു, ഒപ്പം ട്രക്കിലെ ഇന്ധനത്തിന്റെ അളവിനെ കറർ ഫ്യൂവൽ പ്രതിനിധീകരിക്കുന്നു.
  2. ആദ്യത്തെ പെട്രോൾ പമ്പിനെ ക്യൂവിലേക്ക് നീക്കുക, ഒപ്പം ഇന്ധനം വർദ്ധിപ്പിക്കുക (ഇന്ധനം [0] - വില [0]) ഇൻക്രിമെന്റ് അവസാനം.
  3. എല്ലാ പെട്രോൾ പമ്പുകളും ക്യൂവിലേക്ക് ചേർക്കാത്തതുവരെ അല്ലെങ്കിൽ പരിഹാരമില്ലെന്ന് കണ്ടെത്തുന്നതുവരെ അടുത്ത ഘട്ടങ്ങൾ ആവർത്തിക്കുക.
  4. CurrFuel- ന്റെ മൂല്യം നെഗറ്റീവ് ആണെങ്കിൽ, ക്യൂവിൽ നിന്ന് ആരംഭിക്കുന്ന സ്ഥലത്ത് പെട്രോൾ പമ്പ് പോപ്പ് out ട്ട് ചെയ്യുക, ഒപ്പം currFuel (ഇന്ധനം [ആരംഭിക്കുക] - ചെലവ് [ആരംഭം]) വർദ്ധിപ്പിക്കുക ആരംഭിക്കുക. ആരംഭം 0 ആണെങ്കിൽ, സാധ്യമായ പരിഹാരമില്ല, മടങ്ങുക -1.
  5. മറ്റൊന്ന് ക്യൂവിലേക്ക് സ്ഥാനത്ത് പെട്രോൾ പമ്പ് ചേർക്കുക, വർദ്ധിപ്പിക്കുക (ഇന്ധനം [അവസാനം] - ചെലവ് [അവസാനം]), ഇൻക്രിമെന്റ് അവസാനം.
  6. എല്ലാ പെട്രോൾ പമ്പുകളും ക്യൂവിൽ ഉണ്ടെങ്കിൽ, അതായത് ആരംഭിക്കുന്നത് ആരംഭിക്കുന്നതിന് തുല്യമാണ്, ആരംഭം മടങ്ങുക.

കോഡ്

എല്ലാ പെട്രോൾ പമ്പുകളും സന്ദർശിക്കുന്ന ആദ്യത്തെ സർക്കുലർ ടൂർ കണ്ടെത്തുന്നതിനുള്ള ജാവ കോഡ്

class FindTheFirstCircularTourThatVisitsAllThePetrolPumps {
    private static int findPetrolPump(int[] fuel, int[] costs) {
        // total number of petrol pumps
        int n = fuel.length;

        // initialize start and end as 0
        int start = 0, end = 0;
        // initialize currFuel as 0
        int currFuel = 0;
        // push the first petrol pump to queue
        currFuel += (fuel[end] - costs[end]);
        // increment end
        end = (end + 1) % n;

        while (end != start || currFuel < 0)  {
            // if currFuel becomes negative, one by one pop out
            // petrol pumps from queue
            while (currFuel < 0) {
                currFuel -= (fuel[start] - costs[start]);
                start = (start + 1) % n;
                // if start again becomes 0, there is no possible solution
                if (start == 0) {
                    return -1;
                }
            }

            // Push the current petrol pump to queue and update currFuel
            currFuel += (fuel[end] - costs[end]);
            end = (end + 1) % n;
        }

        // return the start point
        return (start + 1);
    }

    public static void main(String[] args) {
        // Example 1
        int fuel1[] = new int[] {5, 2, 11, 8};
        int costs1[] = new int[] {3, 7, 2, 9};
        System.out.println(findPetrolPump(fuel1,costs1));

        // Example 2
        int fuel2[] = new int[] {1, 2, 1, 3};
        int costs2[] = new int[] {1, 2, 2, 1};
        System.out.println(findPetrolPump(fuel2, costs2));

        // Example 3
        int fuel3[] = new int[] {2, 4, 1, 3};
        int costs3[] = new int[] {3, 5, 1, 3};
        System.out.println(findPetrolPump(fuel3, costs3));
    }
}
3
4
-1

എല്ലാ പെട്രോൾ പമ്പുകളും സന്ദർശിക്കുന്ന ആദ്യത്തെ സർക്കുലർ ടൂർ കണ്ടെത്തുന്നതിനുള്ള സി ++ കോഡ്

#include <iostream>
using namespace std;

int findPetrolPump(int *fuel, int *costs, int n) {
    // initialize start and end as 0
    int start = 0, end = 0;
    // initialize currFuel as 0
    int currFuel = 0;
    // push the first petrol pump to queue
    currFuel += (fuel[end] - costs[end]);
    // increment end
    end = (end + 1) % n;
    
    while(end != start || currFuel < 0) {
        // if currFuel becomes negative, one by one pop out
        // petrol pumps from queue
        while (currFuel < 0) {
            currFuel -= (fuel[start] - costs[start]);
            start = (start + 1) % n;
            // if start again becomes 0, there is no possible solution
            if (start == 0) {
                return -1;
            }
        }
        
        // Push the current petrol pump to queue and update currFuel
        currFuel += (fuel[end] - costs[end]);
        end = (end + 1) % n;
    }
    
    // return the start point
    return (start + 1);
}

int main() {
  // Example 1
    int fuel1[] = {5, 2, 11, 8};
    int costs1[] = {3, 7, 2, 9};
    cout<<findPetrolPump(fuel1, costs1, sizeof(fuel1) / sizeof(fuel1[0]))<<endl;

    // Example 2
    int fuel2[] = {1, 2, 1, 3};
    int costs2[] = {1, 2, 2, 1};
    cout<<findPetrolPump(fuel2, costs2, sizeof(fuel2) / sizeof(fuel2[0]))<<endl;

    // Example 3
    int fuel3[] = {2, 4, 1, 3};
    int costs3[] = {3, 5, 1, 3};
    cout<<findPetrolPump(fuel3, costs3, sizeof(fuel3) / sizeof(fuel3[0]))<<endl;
  
  return 0;
}
3
4
-1

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത 

O (n), ക്യൂ ഉപയോഗിക്കുന്നത് ഞങ്ങളുടെ സമയം ലാഭിക്കുകയും ലീനിയർ സമയത്ത് പ്രശ്നം പരിഹരിക്കാൻ ഞങ്ങൾക്ക് കഴിയുകയും ചെയ്യുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), ഞങ്ങൾ ഒരു ക്യൂ ഉപയോഗിക്കുന്നു, അത് ഞങ്ങൾക്ക് ലീനിയർ സ്പേസ് സങ്കീർണ്ണത നഷ്ടപ്പെടുത്തും. പക്ഷേ, അതിനുപകരം, പ്രാരംഭ ഇൻപുട്ട് അറേകൾ ക്യൂകളായി ഉപയോഗിക്കാൻ ഞങ്ങൾ പോയിന്ററുകൾ ഉപയോഗിച്ചു. അങ്ങനെ ഞങ്ങൾക്ക് സ്ഥലം ലാഭിക്കുന്നു.