ಜನರಿಗೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಕ್ಯಾಂಡಿಗಳನ್ನು ವಿತರಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಬೈನರಿ ಹುಡುಕಾಟ ಮಠ

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

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಎರಡು ಸಂಖ್ಯೆಗಳನ್ನು ನೀಡಲಾಗುತ್ತದೆ ಮಿಠಾಯಿಗಳು ಮತ್ತು ಸಂಖ್ಯೆ_ ಜನರು. ಮೊದಲ ಸಂಖ್ಯೆಯ ಮಿಠಾಯಿಗಳು ನಮ್ಮಲ್ಲಿರುವ ಮಿಠಾಯಿಗಳ ಸಂಖ್ಯೆ. ನಾವು ಮಿಠಾಯಿಗಳನ್ನು ವಿತರಿಸಬೇಕಾದ ವ್ಯಕ್ತಿಯ ಸಂಖ್ಯೆಯನ್ನು num_people ತೋರಿಸುತ್ತದೆ.

ಮಿಠಾಯಿಗಳ ವಿತರಣೆಯ ನಿಯಮ ಹೀಗಿದೆ:
ನಾವು ಎಡಗಡೆಯ ವ್ಯಕ್ತಿಯಿಂದ 1 ಕ್ಯಾಂಡಿಯನ್ನು ಕೊಡುತ್ತೇವೆ, ನಂತರ ನಾವು 2 ಕ್ಯಾಂಡಿಗಳನ್ನು 2 ನೇ ವ್ಯಕ್ತಿಗೆ, 3 ಕ್ಯಾಂಡಿಗಳನ್ನು 3 ನೇ ವ್ಯಕ್ತಿಗೆ n ಕ್ಯಾಂಡೀಸ್ ತನಕ n ನೇ ವ್ಯಕ್ತಿಗೆ ನೀಡುತ್ತೇವೆ. ಅದರ ನಂತರ ನಾವು ಮತ್ತೆ ಎಡಗೈ ವ್ಯಕ್ತಿಯಿಂದ n + 1 ಮಿಠಾಯಿಗಳನ್ನು ಕೊಟ್ಟು n + 2, n + 3 ಅನ್ನು ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ. ನಾವು ಮಿಠಾಯಿಗಳು ಮುಗಿಯುವವರೆಗೂ ಈ ಚಕ್ರದ ವಿತರಣೆಯು ಮುಂದುವರಿಯುತ್ತದೆ, ಅಂದರೆ ನಮ್ಮ ಉಳಿದ ಮಿಠಾಯಿಗಳು ಪ್ರಸ್ತುತ ಅಗತ್ಯಕ್ಕಿಂತ ಕಡಿಮೆಯಾದಾಗ, ಉಳಿದ ಮಿಠಾಯಿಗಳನ್ನು ನಾವು ಪ್ರಸ್ತುತ ವ್ಯಕ್ತಿಗೆ ನೀಡುತ್ತೇವೆ ಮತ್ತು ನಂತರ ನಾವು ನಿಲ್ಲಿಸುತ್ತೇವೆ.

ಉದಾಹರಣೆ

candies = 7, num_people = 4
[1,2,3,1]

ವಿವರಣೆ:

ಮೊದಲ ತಿರುವಿನಲ್ಲಿ, ಉತ್ತರ [0] + = 1, ಮತ್ತು ರಚನೆಯು [1,0,0,0] ಆಗಿದೆ.
ಎರಡನೇ ತಿರುವಿನಲ್ಲಿ, ಉತ್ತರ [1] + = 2, ಮತ್ತು ರಚನೆಯು [1,2,0,0] ಆಗಿದೆ.
ಮೂರನೇ ತಿರುವು, ಉತ್ತರ [2] + = 3, ಮತ್ತು ರಚನೆಯು [1,2,3,0].
ನಾಲ್ಕನೇ ತಿರುವು, ಅನ್ಸ್ [3] + = 1 (ಏಕೆಂದರೆ ಕೇವಲ ಒಂದು ಕ್ಯಾಂಡಿ ಮಾತ್ರ ಉಳಿದಿದೆ), ಮತ್ತು ಅಂತಿಮ ರಚನೆಯು [1,2,3,1] ಆಗಿದೆ.

candies = 10, num_people = 3
[5,2,3]

ವಿವರಣೆ:

ಮೊದಲ ತಿರುವಿನಲ್ಲಿ, ಉತ್ತರ [0] + = 1, ಮತ್ತು ರಚನೆಯು [1,0,0] ಆಗಿದೆ.
ಎರಡನೇ ತಿರುವಿನಲ್ಲಿ, ಉತ್ತರ [1] + = 2, ಮತ್ತು ರಚನೆಯು [1,2,0] ಆಗಿದೆ.
ಮೂರನೇ ತಿರುವು, ಉತ್ತರ [2] + = 3, ಮತ್ತು ರಚನೆಯು [1,2,3].
ನಾಲ್ಕನೇ ತಿರುವು, ಉತ್ತರ [0] + = 4, ಮತ್ತು ಅಂತಿಮ ರಚನೆಯು [5,2,3].

ಅಪ್ರೋಚ್ 1 (ವಿವೇಚನಾರಹಿತ ಶಕ್ತಿ)

ಮೊದಲ ವ್ಯಕ್ತಿಗೆ ಎಲ್ ಕ್ಯಾಂಡಿ ಕೊಡುವುದು ಮತ್ತು 2 ರಿಂದ 2 ನೇ ವ್ಯಕ್ತಿಗೆ ಕೊಡುವುದು ಮತ್ತು ಕೊನೆಯ ವ್ಯಕ್ತಿಗೆ ಹೋಗುವುದು ಸರಳ ವಿಧಾನವಾಗಿದೆ. ನಂತರ ಮತ್ತೆ ಮೊದಲ ವ್ಯಕ್ತಿಗೆ ಅನುಗುಣವಾಗಿ ಮಿಠಾಯಿಗಳನ್ನು ನೀಡಿ ಪ್ರಾರಂಭಿಸಿ.
ಇದನ್ನು ಬಳಸಿಕೊಂಡು ಇದನ್ನು ಮಾಡಬಹುದು ನೆಸ್ಟೆಡ್ ಲೂಪ್, ಇದರಲ್ಲಿ ಯಾವುದೇ ಕ್ಯಾಂಡಿ ಉಳಿದಿರುವ ಅಥವಾ ಇಲ್ಲದಿರುವ ಸ್ಥಿತಿಗೆ ಹೊರಗಿನ ಲೂಪ್ ಚಲಿಸುತ್ತದೆ. ಆಂತರಿಕ ಲೂಪ್ ಎಡದಿಂದ ಬಲಕ್ಕೆ ಚಲಿಸುತ್ತದೆ, ಅದು ನೀಡಬೇಕಾದ ಪ್ರಸ್ತುತ ಮಿಠಾಯಿಗಳೊಂದಿಗೆ ಪ್ರತಿ ಸ್ಥಾನದ ಮೌಲ್ಯಗಳನ್ನು ಒಟ್ಟುಗೂಡಿಸುತ್ತದೆ. ಆದರೆ ಪ್ರಸ್ತುತ ಉಳಿದಿರುವ ಮಿಠಾಯಿಗಳು ಪ್ರಸ್ತುತ ಅಗತ್ಯಕ್ಕಿಂತ ಚಿಕ್ಕದಾಗಿರುವಂತಹ ಪರಿಸ್ಥಿತಿ ಇರಬಹುದು. ಹೀಗಾಗಿ, ಆಂತರಿಕ ಲೂಪ್ನಲ್ಲಿ ಬೇರೆ ವೇಳೆ ಸ್ಥಿತಿ ಇದೆ.

ಪ್ರಸ್ತುತ ಅಗತ್ಯವಿರುವ ಮಿಠಾಯಿಗಳು ಉಳಿದ ಮಿಠಾಯಿಗಳಿಗಿಂತ ಹೆಚ್ಚಾದಾಗ, ಉಳಿದ ಮಿಠಾಯಿಗಳನ್ನು ಪ್ರಸ್ತುತ ವ್ಯಕ್ತಿಗೆ ನೀಡಲಾಗುತ್ತದೆ. ಇಲ್ಲದಿದ್ದರೆ, ಪ್ರಸ್ತುತ ಅಗತ್ಯವಿರುವ ಮಿಠಾಯಿಗಳನ್ನು ಪ್ರಸ್ತುತ ವ್ಯಕ್ತಿಗೆ ನೀಡಲಾಗುತ್ತದೆ.

ಜನರಿಗೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಕ್ಯಾಂಡಿಗಳನ್ನು ವಿತರಿಸಲು ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <iostream>
#include <vector>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
        vector<int>ans;
        /*
        initially everyone has no candy. Thus, answer array is filled up with zeros.
        */
        for(int i=0;i<num_people;i++){
            ans.push_back(0);
        }
        int cur=0;//current requirement is initialized to zero
        while(candies>0){
            for(int i=0;i<num_people;i++){
                cur++; //current requirement increments by one each time.
                if(candies>=cur){ //checks if the remaining candies are greater than current requirement 
                ans[i]+=cur;
                candies-=cur;
                }else{
                    ans[i]+=candies;
                    candies=0;
                }
            }
        }
        return ans;
    }
int main()
{
    int candies=10,num_people=3;
    vector<int>ans=distributeCandies(candies, num_people);
    for(int i:ans)cout<<(i)<<" ";
}
5 2 3

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int candies=10, num_people=3;
        int[]ans=distributeCandies(candies, num_people);
        for(int i:ans)System.out.print(i+" ");
    }
    public static  int[] distributeCandies(int candies, int num_people) {
        int[]ans=new int[num_people];
        Arrays.fill(ans,0);
        int cur=0;
        while(candies>0){
            for(int i=0;i<num_people;i++){
                cur++;
                if(candies>=cur){
                ans[i]+=cur;
                candies-=cur;
                }else{
                    ans[i]+=candies;
                    candies=0;
                }
            }
        }
        return ans;
    }
}
5 2 3

ಜನರಿಗೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಕ್ಯಾಂಡಿಗಳನ್ನು ವಿತರಿಸಲು ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

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

ಒ (ಗರಿಷ್ಠ (ಚದರ (ಮಿಠಾಯಿಗಳು)): ಪ್ರಸ್ತುತ ಅಗತ್ಯವು ಪ್ರತಿ ಲೂಪ್‌ನಲ್ಲಿ ಒಂದರಿಂದ ಹೆಚ್ಚಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ, ಮಿಠಾಯಿಗಳ ಸಂಖ್ಯೆ ಮೊದಲು 1 ರಿಂದ ಕಡಿಮೆಯಾಗುತ್ತದೆ ಮತ್ತು ನಂತರ 2 ರಿಂದ ಕಡಿಮೆಯಾಗುತ್ತದೆ.
ಆದ್ದರಿಂದ, ಸಮಯದ ನಂತರ, ಕೈಬಿಟ್ಟ ಮಿಠಾಯಿಗಳ ಸಂಖ್ಯೆ ಟಿ * (ಟಿ + 1) / 2 ಅಥವಾ ಟಿ ಟಿ ನಂತರ ಮಿಠಾಯಿಗಳನ್ನು ಬಿಡಲಾಗುತ್ತದೆ.
ಹೀಗೆ ಸಿ ಮಿಠಾಯಿಗಳನ್ನು ಬಿಡಲು ನಮಗೆ ಚದರ (ಸಿ) ಸಮಯ ಬೇಕು.
ಹೀಗಾಗಿ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಚದರ (ಮಿಠಾಯಿಗಳು) ಆಗಿದೆ.

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

ಒ (ಸಂಖ್ಯೆ_ ಜನರು): ಸಂಖ್ಯೆ_ಪೀಪಲ್ ಗಾತ್ರದ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ, ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯು O (num_people) ಆಗಿದೆ.

ಅಪ್ರೋಚ್ 2 (ಬೈನರಿ ಹುಡುಕಾಟ)

ಹಿಂದಿನ ವಿಧಾನದಲ್ಲಿ, ನಾವು ಪ್ರತಿಯೊಬ್ಬರಿಗೂ ಮಿಠಾಯಿಗಳನ್ನು ಒಂದೊಂದಾಗಿ ನೀಡುತ್ತಿದ್ದೆವು. ನಂತರ, ಮತ್ತೆ ನಾವು ಚಕ್ರದಿಂದ ಪ್ರಾರಂಭದಿಂದ ಮಿಠಾಯಿಗಳನ್ನು ನೀಡಲು ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ. ಇದು ಖಂಡಿತವಾಗಿಯೂ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುವ ಪ್ರಕ್ರಿಯೆ.
ಆದ್ದರಿಂದ, ಈ ವಿಧಾನದಲ್ಲಿ, ನಾವು ಮೂಲತಃ ಈ ಕೆಳಗಿನ ಹಂತಗಳನ್ನು ನಿರ್ವಹಿಸುತ್ತೇವೆ.

ಮೊದಲನೆಯದಾಗಿ, ಮಿಠಾಯಿಗಳ ಸಂಪೂರ್ಣ ನೆರವೇರಿಕೆಯ ಒಟ್ಟು ಸಂಖ್ಯೆಯನ್ನು ನಾವು ಲೆಕ್ಕ ಹಾಕುತ್ತೇವೆ. ಅಂದರೆ ನಿಯಮದ ಪ್ರಕಾರ ನಿಖರವಾದ ಮಿಠಾಯಿಗಳನ್ನು ಪಡೆಯುವ ಒಟ್ಟು ಜನರನ್ನು ನಾವು ಕಂಡುಕೊಳ್ಳುತ್ತೇವೆ.
ವಿತರಣೆಯು 1 ರಿಂದ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ ಮತ್ತು 1 ರಿಂದ ಹೆಚ್ಚಾಗುತ್ತದೆ. ಹೀಗೆ ವಿತರಣೆಯು 1 2 3 4 5 6 ಆಗಿರಬೇಕು. ಈಗ ನಾವು ಮಿಠಾಯಿಗಳನ್ನು 6 ಬಾರಿ ಯಶಸ್ವಿಯಾಗಿ ನೀಡಿದ್ದೇವೆ ಎಂದು ಭಾವಿಸೋಣ. ನಂತರ ಸೇವಿಸುವ ಒಟ್ಟು ಮಿಠಾಯಿಗಳ ಸಂಖ್ಯೆ ಮೊದಲ 6 ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳ ಮೊತ್ತವಾಗಿದೆ.
ಆದ್ದರಿಂದ ನಾವು ಯಾವುದೇ ಸಮಯದಲ್ಲಿ, ಸೇವಿಸುವ ಮಿಠಾಯಿಗಳ ಸಂಖ್ಯೆಯು n ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳ ಮೊತ್ತವಾಗಿದೆ ಎಂದು ಹೇಳಬಹುದು, ಅಲ್ಲಿ n ಎಂಬುದು ಆ ಹಂತದವರೆಗೆ ವಿತರಣೆಯಾಗಿದೆ.
ಈಗ ನಾವು ನಿಯಮದ ಪ್ರಕಾರ ಗರಿಷ್ಠ ಯಶಸ್ವಿ ವಿತರಣೆಯನ್ನು ಬಯಸುತ್ತೇವೆ. ಅಂದರೆ ನಾವು n ನ ಗರಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ಬಯಸುತ್ತೇವೆ ಅಂದರೆ n (n + 1) / 2 <= ಒಟ್ಟು ಮಿಠಾಯಿಗಳ ಸಂಖ್ಯೆ.

N ನ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಲು, ನಾವು ಅನೇಕ ವಿಧಾನಗಳನ್ನು ಹೊಂದಿದ್ದೇವೆ. ನಾವು n ಗಾಗಿ ಚತುರ್ಭುಜ ಕಾರ್ಯವನ್ನು ಪರಿಹರಿಸಬಹುದು ಅಥವಾ ನಾವು n = 1 ಗಾಗಿ ಪ್ರಾರಂಭಿಸಬಹುದು ಮತ್ತು n ನ ಮೌಲ್ಯವನ್ನು 1 ರಿಂದ ರೇಖೀಯವಾಗಿ ಹೆಚ್ಚಿಸುವ ಮೂಲಕ n ನ ಮೌಲ್ಯವನ್ನು ಬದಲಿಸಬಹುದು. ಆದರೆ ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಇಲ್ಲಿ ಬಳಸುವುದು ಅತ್ಯಂತ ಸೂಕ್ತವಾದ ಪರಿಹಾರವಾಗಿದೆ.

N ನ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಬೈನರಿ ಹುಡುಕಾಟ.

ಇಲ್ಲಿ ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಬಳಸಲು, n ಯಾವ ಬರಬಹುದು ಎಂಬುದನ್ನು ನಾವು ತಿಳಿದಿರಬೇಕು. N ನ ಕನಿಷ್ಠ ಮೌಲ್ಯವು 1 ಆಗಿರಬಹುದು ಎಂದು ನಾವು ಹೇಳಬಹುದು, ಏಕೆಂದರೆ ಮಿಠಾಯಿಗಳ ನಿರ್ಬಂಧವು ಕನಿಷ್ಠ 1 ಆಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ನಾವು ಕನಿಷ್ಟ 1 ಕ್ಯಾಂಡಿಯನ್ನು ಮೊದಲ ವ್ಯಕ್ತಿಗೆ ನೀಡಬಹುದು, ಆದ್ದರಿಂದ ಒಂದು ಯಶಸ್ವಿ ವಿತರಣೆಯನ್ನು ಮಾಡುತ್ತೇವೆ (ಆದ್ದರಿಂದ, ಕಡಿಮೆ ಬೌಂಡ್ l = 1) . N ನ ಮೇಲಿನ ಬೌಂಡ್ ಅನ್ನು ಲೆಕ್ಕಹಾಕಲು ಸಂಕೀರ್ಣವಾಗಬಹುದು, ಆದ್ದರಿಂದ ನಾವು ಅದನ್ನು ನಮ್ಮಿಂದಲೇ ದೊಡ್ಡದಾದ ಪೂರ್ಣಾಂಕ ಮೌಲ್ಯವನ್ನು ನೀಡುತ್ತಿದ್ದೇವೆ (ಮೇಲಿನ ಬೌಂಡ್ r = 1000000 ಅನ್ನು ಬಿಡಿ).

ಈಗ ನಾವು l ಮತ್ತು r ನಡುವಿನ ಪಾಯಿಂಟ್ n ಅನ್ನು ಬಯಸುತ್ತೇವೆ ಅದು ಸಮೀಕರಣವನ್ನು ಪೂರೈಸುವ ಗರಿಷ್ಠ ಮೌಲ್ಯವಾಗಿದೆ.
n (n + 1) / 2 <= ಮಿಠಾಯಿಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆ.
L ಮತ್ತು r ನಡುವಿನ ಯಾವುದೇ ಬಿಂದು (ಒಂದು ಬಿಂದುವನ್ನು ಮಧ್ಯದಲ್ಲಿ ಬಿಡಿ) ಮೇಲಿನ ಸಮೀಕರಣವನ್ನು ತೃಪ್ತಿಪಡಿಸಿದರೆ. ಮತ್ತು ಮುಂದಿನ ಹಂತವು (ಅಂದರೆ ಮಧ್ಯ +1) ಸಮೀಕರಣವನ್ನು ಪೂರೈಸಲು ಸಾಧ್ಯವಿಲ್ಲ. ನಂತರ ಮಧ್ಯವು ಯಶಸ್ವಿ ವಿತರಣೆಯ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯಾಗಿರುತ್ತದೆ.

ಯಶಸ್ವಿ ನೆರವೇರಿಕೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ನಾವು ಕಂಡುಕೊಂಡ ನಂತರ (ಮಧ್ಯ), ವಿತರಣೆಯ ಸಂಪೂರ್ಣ ಚಕ್ರಗಳ ಸಂಖ್ಯೆಯನ್ನು ನಾವು ಸುಲಭವಾಗಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು, ಅದು k = mid /ಸಂಖ್ಯೆ_ ಜನರು.

ಕೆ ಸಂಪೂರ್ಣ ಚಕ್ರಗಳ ನಂತರ ಈಗ ನಾವು ಪ್ರತಿಯೊಬ್ಬ ವ್ಯಕ್ತಿಗೆ ಮಿಠಾಯಿಗಳನ್ನು ಲೆಕ್ಕ ಹಾಕುತ್ತಿದ್ದೇವೆ.

ಜನರಿಗೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಕ್ಯಾಂಡಿಗಳನ್ನು ವಿತರಿಸಿ

 

ಆದ್ದರಿಂದ, ಕೆ ಸಂಪೂರ್ಣ ಚಕ್ರಗಳ ನಂತರ ಮಿಠಾಯಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಲೆಕ್ಕಹಾಕಲು ನಾವು ಗಣಿತದ ಪದಗಳನ್ನು ಕಂಡುಕೊಂಡಿದ್ದೇವೆ. ಕೆ + 1 ನೇ ಅಪೂರ್ಣ ಚಕ್ರದ ಬಗ್ಗೆ ಏನು.
ಕೆ +1 ನೇ ಅಪೂರ್ಣ ಚಕ್ರದಲ್ಲಿ, ಮಿಠಾಯಿಗಳ ಯಶಸ್ವಿ ನೆರವೇರಿಕೆ n ನೇ ಜನರಿಗೆ ಹೋಗುವುದಿಲ್ಲ ಎಂದು ನಾವು ಸುಲಭವಾಗಿ ಹೇಳಬಹುದು, ನಮ್ಮ ಮಿಠಾಯಿಗಳು ಈ ನಡುವೆ ಎಲ್ಲೋ ಮುಗಿಯುತ್ತವೆ.

ನಮ್ಮ ಕೊನೆಯ ಯಶಸ್ವಿ ನೆರವೇರಿಕೆ ಮಧ್ಯದಲ್ಲಿದೆ ಎಂದು ನಾವು ಈಗಾಗಲೇ ಲೆಕ್ಕ ಹಾಕಿದ್ದೇವೆ. ಮತ್ತು ಮಧ್ಯ%ಸಂಖ್ಯೆ_ ಜನರು ವ್ಯಕ್ತಿಯು ಆ ಮಧ್ಯದ ಮಿಠಾಯಿಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತಿದ್ದಾನೆ. ಮತ್ತು ಮುಂದಿನ ವ್ಯಕ್ತಿಯು ಉಳಿದ ಎಲ್ಲಾ ಮಿಠಾಯಿಗಳನ್ನು ಪಡೆಯುತ್ತಾನೆ.

ಜನರಿಗೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಕ್ಯಾಂಡಿಗಳನ್ನು ವಿತರಿಸಿ
ಹೀಗೆ ನಾವು ಈ ಕೊನೆಯ ಅಪೂರ್ಣ ಚಕ್ರ ವಿತರಣೆಯನ್ನು ನಮ್ಮ ಮೊದಲ ಮಧ್ಯ% ಗೆ ಸೇರಿಸುತ್ತೇವೆಸಂಖ್ಯೆ_ ಜನರು ಮತ್ತು 1 + ಮಧ್ಯ%ಸಂಖ್ಯೆ_ ಜನರು ಉಳಿದ ಎಲ್ಲಾ ಮಿಠಾಯಿಗಳನ್ನು ಪಡೆಯುತ್ತದೆ.

ಜನರಿಗೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಕ್ಯಾಂಡಿಗಳನ್ನು ವಿತರಿಸಲು ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <iostream>
#include <vector>
using namespace std;
vector<int> distributeCandies(int candies, int num_people) {
        long l=0,r=1000000;
        long mid=0;
        /*
        searching the last successful fulfilment point mid
        */
        while(l<=r){
            mid=l+(r-l)/2;
            long a=((mid+1)*(mid))/2;
            long c=((mid+2)*(mid+1))/2;
            if(a<=candies && c>candies)break;
            else if(a>candies)r=mid;
            else l=mid;
        }
        long k=mid/num_people;
        /*
        here k is the number of complete cycles
        */
        long ans[num_people];
        int i=0;
        for(i=0;i<num_people;i++){
            ans[i]=((k*(k-1)*num_people)/2)+(i+1)*k;//calculating the number of candies to each person after k complete cycles.
        }
        for(i=0;i<mid%num_people;i++){
            ans[i]+=((k*num_people)+i+1);//giving candies to first mid%num_people in k+1 th incomplete cycle.
        }
        ans[i%num_people]+=candies-(mid*(mid+1)/2);// giving all the remaining candies to next person 
        vector<int> ans1;
        for(i=0;i<num_people;i++){
            ans1.push_back((int)(ans[i]));
        }
        return ans1;
        
    }
int main()
{
    int candies=10,num_people=3;
    vector<int>ans=distributeCandies(candies, num_people);
    for(int i:ans)cout<<(i)<<" ";
}
5 2 3

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int candies=10, num_people=3;
        int[]ans=distributeCandies(candies, num_people);
        for(int i:ans)System.out.print(i+" ");
    }
    public static  int[] distributeCandies(int candies, int num_people) {
       
        long l=0,r=1000000;
        long mid=0;
        /*
        searching the last successful fulfilment point mid
        */
        while(l<=r){
            mid=l+(r-l)/2;
            long a=((mid+1)*(mid))/2;
            long c=((mid+2)*(mid+1))/2;
            if(a<=candies && c>candies)break;
            else if(a>candies)r=mid;
            else l=mid;
        }
        long k=mid/num_people;
        /*
        here k is the number of complete cycles
        */
        long[]ans=new long[num_people];
        int i=0;
        for(i=0;i<num_people;i++){
            ans[i]=((k*(k-1)*num_people)/2)+(i+1)*k;//calculating the number of candies to each person after k complete cycles.
        }
        for(i=0;i<mid%num_people;i++){
            ans[i]+=((k*num_people)+i+1);//giving candies to first mid%num_people in k+1 th incomplete cycle.
        }
        ans[i%num_people]+=candies-(mid*(mid+1)/2);// giving all the remaining candies to next person
        int[]ans1=new int[num_people];
        for(i=0;i<ans1.length;i++){
            ans1[i]=(int)(ans[i]);
        }
        return ans1;
    }
}
5 2 3

ಜನರಿಗೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಕ್ಯಾಂಡಿಗಳನ್ನು ವಿತರಿಸಲು ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

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

ಒ (ಸಂಖ್ಯೆ_ ಜನರು):  ಯಶಸ್ವಿ ನೆರವೇರಿಕೆಯ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು, ನಾವು ಸ್ವಲ್ಪ ಸಮಯದ ಲೂಪ್ ಅನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ, ಅದು ಲಾಗ್ (10 ^ 6) ಬಾರಿ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ 32 ರ ಆಸುಪಾಸಿನಲ್ಲಿ ಚಲಿಸುತ್ತದೆ. ನಂತರ ನಾವು ಲೂಪ್ ಅನ್ನು ರೇಖೀಯವಾಗಿ ಸಂಖ್ಯೆ_ಪೀಪಲ್ ಬಾರಿ ಓಡಿಸಿದ್ದೇವೆ. ಆದ್ದರಿಂದ, ಸಮಯ ಪೂರ್ಣಗೊಳಿಸುವಿಕೆಯು O (num_people + 32) ಅಥವಾ O (num_people) ಆಗಿದೆ.

ಗಮನಿಸಿ: ಮಿಠಾಯಿಗಳ ಸಂಖ್ಯೆ ಜನರ ಸಂಖ್ಯೆಗಿಂತ ಹೆಚ್ಚಾದಾಗ ಈ ಅಲ್ಗಾರಿದಮ್ ಉತ್ತಮವಾಗಿರುತ್ತದೆ. ಏಕೆಂದರೆ, ಈ ಅಲ್ಗಾರಿದಮ್ ಮಿಠಾಯಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಅವಲಂಬಿಸಿರುವುದಿಲ್ಲ.

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

ಒ (ಸಂಖ್ಯೆ_ ಜನರು): ಸಂಖ್ಯೆ_ಪೀಪಲ್ ಗಾತ್ರದ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ, ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯು O (num_people) ಆಗಿದೆ.