ಮಧ್ಯಂತರ ಶ್ರೇಣಿ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಬೆಸ ಸಂಖ್ಯೆಗಳನ್ನು ಎಣಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಮೈಕ್ರೋಸಾಫ್ಟ್
ಮಠ

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

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಕಡಿಮೆ ಮತ್ತು ಹೆಚ್ಚಿನ ಎರಡು negative ಣಾತ್ಮಕವಲ್ಲದ ಪೂರ್ಣಾಂಕಗಳನ್ನು ನೀಡಲಾಗುತ್ತದೆ. ನಿರ್ದಿಷ್ಟ ಮಧ್ಯಂತರ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ [ಕಡಿಮೆ, ಹೆಚ್ಚಿನ] ಎಷ್ಟು ಬೆಸ ಸಂಖ್ಯೆಗಳಿವೆ ಎಂದು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ.

ಉದಾಹರಣೆ

low = 3, high = 7
3

ವಿವರಣೆ:

3 ಮತ್ತು 7 ರ ನಡುವಿನ ಬೆಸ ಸಂಖ್ಯೆಗಳು [3, 5, 7].

low = 8, high = 10
1

ವಿವರಣೆ:

8 ಮತ್ತು 10 ರ ನಡುವಿನ ಬೆಸ ಸಂಖ್ಯೆಗಳು [9].

ಅಪ್ರೋಚ್

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

ನಿರ್ದಿಷ್ಟ ಮಧ್ಯಂತರ ಶ್ರೇಣಿಯಲ್ಲಿ ಒಟ್ಟು ಬೆಸ ಸಂಖ್ಯೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ತುಂಬಾ ಸುಲಭ, ಏಕೆಂದರೆ ಮಧ್ಯಂತರ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ಅರ್ಧದಷ್ಟು ಮತ್ತು ಅರ್ಧ ಬೆಸ ಸಂಖ್ಯೆಗಳಿವೆ ಎಂದು ನಮಗೆ ತಿಳಿದಿದೆ.
ಆದರೆ ಮಧ್ಯಂತರದ ಗಡಿಗಳನ್ನು ನಾವು ಬಹಳ ಎಚ್ಚರಿಕೆಯಿಂದ ಪರಿಗಣಿಸಬೇಕು. ಆದ್ದರಿಂದ ನಾವು ಏನು ಮಾಡಬಹುದು ಎಂದರೆ ಮೊದಲ n ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳಲ್ಲಿ ಬೆಸ ಸಂಖ್ಯೆಗಳ ಎಣಿಕೆಗೆ ನಾವು ಸೂತ್ರವನ್ನು ರಚಿಸಬಹುದು. ಅದನ್ನು ಎಣಿಸೋಣ [n]. ಕಡಿಮೆ ಮತ್ತು ಹೆಚ್ಚಿನ ನಡುವಿನ ಬೆಸ ಸಂಖ್ಯೆಗಳು ಇದಕ್ಕೆ ಸಮಾನವಾಗಿರುತ್ತದೆ:
ಎಣಿಕೆ [ಕಡಿಮೆ, ಹೆಚ್ಚಿನ] = ಎಣಿಕೆ [ಹೆಚ್ಚಿನ] - ಎಣಿಕೆ [ಕಡಿಮೆ -1].

ಮಧ್ಯಂತರ ಶ್ರೇಣಿ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಬೆಸ ಸಂಖ್ಯೆಗಳನ್ನು ಎಣಿಸಿ

ಈಗ ಎಣಿಕೆಗಾಗಿ ಕೆಲವು ಉದಾಹರಣೆಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತಿದ್ದೇನೆ [i]:

ಎಣಿಕೆ [1] = 1
ಎಣಿಕೆ [2] = 1
ಎಣಿಕೆ [3] = 2
ಎಣಿಕೆ [4] = 2
ಎಣಿಕೆ [5] = 3

ನಾವು ಆ ಸಂಖ್ಯೆಯನ್ನು [n] = (n + 1) / 2 ಎಂದು ed ಹಿಸಬಹುದು
ಆದ್ದರಿಂದ [ಕಡಿಮೆ, ಹೆಚ್ಚಿನ] = (ಹೆಚ್ಚಿನ + 1) / 2 - ಕಡಿಮೆ / 2 ಎಂದು ಎಣಿಸಿ

ಅನುಷ್ಠಾನ

ಮಧ್ಯಂತರ ಶ್ರೇಣಿ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಬೆಸ ಸಂಖ್ಯೆಗಳಿಗಾಗಿ ಸಿ ++ ಪ್ರೋಗ್ರಾಂ (ನಿಷ್ಕಪಟ ಅಪ್ರೋಚ್)

#include <iostream>
using namespace std;

int countOdds(int low, int high) 
{
    int count=0;
    for(int i=low;i<=high;i++)
        if(i%2==1) count++;
        
    return count;
}

int main()
{
    int low=3,high=7;  
    cout<< countOdds(low, high) <<endl;
}
3

ಮಧ್ಯಂತರ ಶ್ರೇಣಿ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಕೌಂಟ್ ಬೆಸ ಸಂಖ್ಯೆಗಳಿಗಾಗಿ ಜಾವಾ ಪ್ರೋಗ್ರಾಂ (ನಿಷ್ಕಪಟ ಅಪ್ರೋಚ್)

class CountOdd
{  
    public static int countOdds(int low, int high) 
    {
        int count=0;
        for(int i=low;i<=high;i++)
            if(i%2==1) count++;
        
        return count;
    }
    
    public static void main(String args[])
    {
        int low=3,high=7;
        System.out.println(countOdds(low, high));
    }
}
3

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ (ಆಪ್ಟಿಮಮ್ ಅಪ್ರೋಚ್)

#include <iostream>
using namespace std;

int countOdds(int low, int high) 
{
   return (high + 1) / 2 - low / 2;       
}

int main()
{
    int low=3,high=7;  
    cout<< countOdds(low, high) <<endl;
}
3

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ (ಆಪ್ಟಿಮಮ್ ಅಪ್ರೋಚ್)

class CountOdd
{  
    public static int countOdds(int low, int high) 
    {
        return (high + 1) / 2 - low / 2;   
    }
    
    public static void main(String args[])
    {
        int low=3,high=7;
        System.out.println(countOdds(low, high));
    }
}
3

ಮಧ್ಯಂತರ ಶ್ರೇಣಿ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಎಣಿಕೆ ಬೆಸ ಸಂಖ್ಯೆಗಳಿಗೆ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

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

ಪ್ರತಿ ಸಂಖ್ಯೆಗೆ ಸಂಚರಿಸುವುದು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಓ (ಎನ್) ಸೂತ್ರವನ್ನು ಬಳಸಿಕೊಂಡು ಉತ್ತರವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವಾಗ ಸಮಯದ ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಒ (1) ಕಾರ್ಯಗತಗೊಳಿಸಲು.

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

ಒ (1): ಉತ್ತರಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಬಳಸಲಾಗುವ ವೇರಿಯೇಬಲ್ ಹೊರತುಪಡಿಸಿ ಎರಡೂ ಪರಿಹಾರಗಳಲ್ಲಿ ಯಾವುದೇ ಹೆಚ್ಚುವರಿ ಸ್ಥಳವನ್ನು ಬಳಸಲಾಗುವುದಿಲ್ಲ.