ಎಲ್ಲಾ ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ಗಳಿಗೆ ಭೇಟಿ ನೀಡುವ ಮೊದಲ ವೃತ್ತಾಕಾರದ ಪ್ರವಾಸವನ್ನು ಹುಡುಕಿ


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಫ್ಯಾಕ್ಟ್‌ಸೆಟ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಮಾರ್ಗನ್ ಸ್ಟಾನ್ಲಿ ಜೊಹೊ
ಕ್ಯೂ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಎಲ್ಲಾ ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ಗಳಿಗೆ ಭೇಟಿ ನೀಡುವ ಮೊದಲ ವೃತ್ತಾಕಾರದ ಪ್ರವಾಸವನ್ನು ಹುಡುಕಿ” ಎಂಬ ಸಮಸ್ಯೆಯು ವೃತ್ತಾಕಾರದ ರಸ್ತೆಯಲ್ಲಿ ಎನ್ ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ಗಳಿವೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಪ್ರತಿ ಪೆಟ್ರೋಲ್ ಪಂಪ್ ಹೊಂದಿರುವ ಪೆಟ್ರೋಲ್ ಮತ್ತು ಎರಡು ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ಗಳ ನಡುವಿನ ಅಂತರವನ್ನು ಸರಿದೂಗಿಸಲು ಬೇಕಾದ ಪೆಟ್ರೋಲ್ ಪ್ರಮಾಣವನ್ನು ನೀಡಲಾಗಿದೆ. ಆದ್ದರಿಂದ ನೀವು ಟ್ರಕ್ ಪ್ರಾರಂಭವಾಗುವ ಮತ್ತು ವೃತ್ತವನ್ನು ಪೂರ್ಣಗೊಳಿಸುವ ಮೊದಲ ಪೆಟ್ರೋಲ್ ಪಂಪ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು.
ಇನ್ಪುಟ್ ಸ್ವರೂಪವು {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 ಎಂದು ಪ್ರಾರಂಭಿಸಿ, ಇದು ಟ್ರಕ್‌ನಲ್ಲಿರುವ ಪೆಟ್ರೋಲ್ ಪ್ರಮಾಣವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ.
  3. ಜೆಟಿ ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ನಿಂದ (ಜೆ + 1) ನೇ ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ಗೆ ಪ್ರಯಾಣಿಸಲು, (ಇಂಧನ [ಜೆ] - ವೆಚ್ಚ [ಜೆ]) ಇಂಧನವನ್ನು ಕರ್ರ್‌ಫ್ಯೂಯಲ್‌ಗೆ ಸೇರಿಸಲಾಗುತ್ತದೆ.
  4. ಇಥ್ ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ನಿಂದ ವೃತ್ತದಲ್ಲಿ ಮುಂದೆ ಪ್ರಯಾಣಿಸಲು ಪ್ರಾರಂಭಿಸಿ ಮತ್ತು ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಹೆಚ್ಚುವರಿ ಇಂಧನವನ್ನು (ಇಂಧನ [ಜೆ] - ವೆಚ್ಚ [ಜೆ]) ಸೇರಿಸಿ, ಕರ್ರ್ ಇಂಧನ> = 0 ಆಗಿರುವಾಗ ಈ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸಿ.
  5. ಟ್ರಕ್ ಎಲ್ಲಾ ಎನ್ ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ಗಳ ಮೂಲಕ ಸಂಚರಿಸಲು ಸಾಧ್ಯವಾದರೆ, ನಾನು ಹಿಂತಿರುಗಿ. ಮುಂದಿನ i ಗೆ ಮುಂದುವರಿಯಿರಿ.
  6. ಟ್ರಕ್ ಇಡೀ ವೃತ್ತವನ್ನು ಹಾದುಹೋಗಲು ನಾನು ಇಲ್ಲದಿದ್ದರೆ, -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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್2), ಸಮಯದ ಸಂಕೀರ್ಣತೆ. ಇಲ್ಲಿ N ಎಂಬುದು ನಿರ್ದಿಷ್ಟ ಇನ್ಪುಟ್ನಲ್ಲಿ ಪೆಟ್ರೋಲ್ ಪಂಪ್ಗಳ ಸಂಖ್ಯೆ. ಇಲ್ಲಿ ನಾವು ಬಹುಪದೀಯ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿದ್ದೇವೆ ಏಕೆಂದರೆ ನಾವು ಪ್ರತಿ ಪೆಟ್ರೋಲ್ ಪಂಪ್ ಅನ್ನು ಪ್ರಾರಂಭದ ಹಂತವೆಂದು ಪರಿಗಣಿಸಿದ್ದೇವೆ. ಪ್ರತಿ ಪೆಟ್ರೋಲ್ ಪಂಪ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿದ ನಂತರ ನಾವು ಸಂಪೂರ್ಣ ಪ್ರವಾಸವನ್ನು ಮಾಡಿದ್ದೇವೆ. ಮತ್ತು ಪ್ರವಾಸದ ಸಮಯದಲ್ಲಿ ಪೆಟ್ರೋಲ್ ಟ್ಯಾಂಕ್ ಖಾಲಿಯಾಗುತ್ತದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಲಾಗಿದೆ. ಆದ್ದರಿಂದ ನಾವು ಎನ್ ಆರಂಭಿಕ ಹಂತಗಳನ್ನು ಹೊಂದಿದ್ದೇವೆ ಮತ್ತು ನಂತರ ಪ್ರತಿ ಪ್ರಾರಂಭದ ಸ್ಥಳವು ಎನ್ -1 ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು O (N ^ 2) ಆಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ಇಲ್ಲಿ ನಾವು ಏಕಕಾಲದಲ್ಲಿ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ಅಗತ್ಯವಿರುವ ಯಾವುದೇ ಮಾಹಿತಿಯನ್ನು ಉಳಿಸಿಲ್ಲ. ಹೀಗಾಗಿ ನಾವು ಹೆಚ್ಚು ಜಾಗವನ್ನು ಬಳಸಿಲ್ಲ. ನಾವು ಸ್ಥಿರ ಸಂಖ್ಯೆಯ ಅಸ್ಥಿರಗಳನ್ನು ಬಳಸಿದ್ದೇವೆ ಅದು ಜಾಗದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಸ್ಥಿರಗೊಳಿಸುತ್ತದೆ.

ಆಪ್ಟಿಮಲ್ ಅಪ್ರೋಚ್

ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವುದು ಸೂಕ್ತವಾದ ಉಪಾಯವಾಗಿದೆ ಕ್ಯೂ. ಕರ್ರ್ ಇಂಧನವನ್ನು 0 ಎಂದು ಪ್ರಾರಂಭಿಸಿ. ಕರ್ರ್ ಇಂಧನ> = 0 ಆಗಿರುವಾಗ ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ಗಳನ್ನು ಕ್ಯೂಗೆ ತಳ್ಳುವುದನ್ನು ಮುಂದುವರಿಸಿ, ಮತ್ತು ಪೆಟ್ರೋಲ್ ಪಂಪ್ ಅನ್ನು ಕ್ಯೂ ಕರ್ರ್‌ಫ್ಯೂಲ್‌ಗೆ ತಳ್ಳಿದ ನಂತರ (ಇಂಧನ [i] - ವೆಚ್ಚ [i]) ಹೆಚ್ಚಾಗುತ್ತದೆ. ಯಾವುದೇ ಕ್ಷಣದಲ್ಲಿ ಕರ್ರ್‌ಫುಯಲ್ negative ಣಾತ್ಮಕವಾಗಿದ್ದರೆ, ಕರ್ರ್‌ಫ್ಯುಯಲ್ .ಣಾತ್ಮಕವಾಗುವವರೆಗೆ ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ಗಳನ್ನು ಒಂದರಿಂದ ಒಂದರಂತೆ ಪಾಪ್ out ಟ್ ಮಾಡಿ. ಎಲ್ಲಾ ಎನ್ ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ಗಳು ಸರದಿಯಲ್ಲಿದ್ದರೆ, ಪ್ರಾರಂಭದ ಹಂತವನ್ನು ಹಿಂತಿರುಗಿ, ಇಲ್ಲದಿದ್ದರೆ ಎನ್ ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ಗಳು ಸರದಿಯಲ್ಲಿರಲು ಯಾವುದೇ ಮಾರ್ಗವಿಲ್ಲದಿದ್ದರೆ, ಹಿಂತಿರುಗಿ -1.

ನಾವು ಇಂಧನ ಮತ್ತು ವೆಚ್ಚದ ಶ್ರೇಣಿಯಲ್ಲಿ ಕ್ಯೂ ಅನ್ನು ರಚಿಸಿದರೆ ಕ್ಯೂ ಬಳಸುವ ಜಾಗವನ್ನು ಉಳಿಸಬಹುದು. ಅರೇಗಳಲ್ಲಿ ಸ್ಟಾರ್ಟ್ ಮತ್ತು ಎಂಡ್ ಪಾಯಿಂಟರ್‌ಗಳನ್ನು ಬಳಸುವ ಮೂಲಕ ಇದನ್ನು ಸಾಧಿಸಬಹುದು.

  1. ಪ್ರಾರಂಭ, ಅಂತ್ಯ ಮತ್ತು ಕರ್ರ್‌ಫ್ಯುಯೆಲ್ ಅನ್ನು 0 ಎಂದು ಪ್ರಾರಂಭಿಸಿ, ಅಲ್ಲಿ ಪ್ರಾರಂಭವು ಟ್ರಕ್‌ನ ಪ್ರಾರಂಭದ ಹಂತವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ, ಅಂತ್ಯವು ಭೇಟಿ ನೀಡಲು ಮುಂದಿನ ಪೆಟ್ರೋಲ್ ಪಂಪ್ ಅನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ ಮತ್ತು ಕರ್ರ್‌ಫ್ಯೂಲ್ ಟ್ರಕ್‌ನಲ್ಲಿನ ಇಂಧನದ ಪ್ರಮಾಣವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ.
  2. ಮೊದಲ ಪೆಟ್ರೋಲ್ ಪಂಪ್ ಅನ್ನು ಕ್ಯೂಗೆ ಒತ್ತಿ ಮತ್ತು ಕರ್ರ್ ಇಂಧನದಿಂದ ಇಂಧನ (0 [ಇಂಧನ] - ವೆಚ್ಚ [0]) ಮತ್ತು ಏರಿಕೆ ಅಂತ್ಯ.
  3. ಎಲ್ಲಾ ಪೆಟ್ರೋಲ್ ಪಂಪ್‌ಗಳನ್ನು ಸರದಿಗೆ ಸೇರಿಸದವರೆಗೆ ಅಥವಾ ಯಾವುದೇ ಪರಿಹಾರವಿಲ್ಲ ಎಂದು ತಿಳಿಯುವವರೆಗೆ ಮುಂದಿನ ಹಂತಗಳನ್ನು ಪುನರಾವರ್ತಿಸಿ.
  4. ಕರ್ರ್‌ಫ್ಯೂಲ್‌ನ ಮೌಲ್ಯವು negative ಣಾತ್ಮಕವಾಗಿದ್ದರೆ, ಸ್ಥಾನದಿಂದ ಪ್ರಾರಂಭದಲ್ಲಿ ಪೆಟ್ರೋಲ್ ಪಂಪ್ ಅನ್ನು ಪಾಪ್ and ಟ್ ಮಾಡಿ ಮತ್ತು ಕರ್ರ್ ಇಂಧನದಿಂದ ಇಳಿಕೆ (ಇಂಧನ [ಪ್ರಾರಂಭ] - ವೆಚ್ಚ [ಪ್ರಾರಂಭ]) ಮತ್ತು ಏರಿಕೆ ಪ್ರಾರಂಭ. ಪ್ರಾರಂಭವು 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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ 

ಒ (ಎನ್), ಕ್ಯೂ ಬಳಸುವುದರಿಂದ ನಮಗೆ ಸಮಯ ಉಳಿತಾಯವಾಗುತ್ತದೆ ಮತ್ತು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ನಮಗೆ ಸಾಧ್ಯವಾಗುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ನಾವು ಕ್ಯೂ ಬಳಸುತ್ತಿದ್ದೇವೆ ಮತ್ತು ಅದು ನಮಗೆ ರೇಖೀಯ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯನ್ನು ವೆಚ್ಚ ಮಾಡುತ್ತದೆ. ಆದರೆ ಅದರ ಬದಲಾಗಿ, ಆರಂಭಿಕ ಇನ್‌ಪುಟ್ ಅರೇಗಳನ್ನು ಕ್ಯೂಗಳಾಗಿ ಬಳಸಲು ನಾವು ಪಾಯಿಂಟರ್‌ಗಳನ್ನು ಬಳಸಿದ್ದೇವೆ. ಹೀಗೆ ನಮಗೆ ಜಾಗವನ್ನು ಉಳಿಸುತ್ತದೆ.