సంఖ్య ఎక్కువ లేదా దిగువ II అంచనా


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ గూగుల్ మైక్రోసాఫ్ట్
అర్రే డైనమిక్ ప్రోగ్రామింగ్

సమస్యల నివేదిక

“గెస్ నంబర్ హయ్యర్ లేదా లోయర్ II” మేము గెస్ గేమ్ అని పిలువబడే ఆట ఆడబోతున్నామని పేర్కొంది. నేను 1 నుండి n వరకు సంఖ్యను ఎంచుకుంటానని ఆట చెబుతుంది. నేను ఎన్నుకోని సంఖ్యను మీరు when హించినప్పుడల్లా, మీరు ఎక్కువ లేదా అంతకంటే తక్కువ సంఖ్యను ఎంచుకుంటారని నేను మీకు చెప్పబోతున్నాను.

మరియు ముఖ్యమైన మరియు ఆసక్తికరమైన భాగం ఏమిటంటే, మీరు తప్పు సంఖ్యను ఎంచుకుంటే, x అని చెప్పండి, అప్పుడు మీరు మొత్తంలో x యూనిట్లను చెల్లించబోతున్నారు. మీరు సరైన సంఖ్యను when హించినప్పుడు మీరు ఆట గెలవాలి, అంటే నేను ఎంచుకున్న సంఖ్య.

ఉదాహరణ

n = 10, నేను 6 ని ఎంచుకుంటాను.

మొదట ఎంచుకోండి: మీరు 2 హిస్తున్నారు, ఇది గొప్పది, దాని కంటే పైకి వెళ్ళండి. మీరు $ 2 చెల్లిస్తారు.

రెండవ ఎంపిక: మీరు 4 హిస్తున్నారు, ఇది గొప్పది, దాని కంటే పైకి వెళ్ళండి. మీరు $ 4 చెల్లిస్తారు.

మూడవ ఎంపిక: మీరు 5 హిస్తున్నారు, ఇది గొప్పది, దాని కంటే పైకి వెళ్ళండి. మీరు $ 5 చెల్లిస్తారు.

మీరు 6 అయిన సరైన సంఖ్యను ఎంచుకున్నందున ఆట ఇప్పుడు ముగిసింది.

మీరు $ 2 + $ 4 + $ 5 = $ 11 చెల్లించడం ముగుస్తుంది.

మీకు n ≥ 1 అనే సంఖ్య ఇవ్వబడితే, మీ వద్ద ఎంత డబ్బు ఉండాలి అని నిర్ణయించండి, తద్వారా ఈ తగినంత మొత్తంతో మీరు ఈ ఆట గెలవబోతున్నారని మీరు భరోసా ఇవ్వవచ్చు.

సంఖ్య ఎక్కువ లేదా దిగువ II అంచనా

గెస్ నంబర్ అధిక లేదా దిగువ II సమస్యకు అల్గోరిథం

1. Declare a 2-d array of size n+1.
2. Set output to the maximum value of an integer.
3. Set val to start + (end – start) / 2.
4. While val is less than or equal to end,
  1. Recursively call the function and find out the maximum between the values and Set table [start][end] to x + maximum of the number below the x value and number greater than the x value.
  2. Find out the minimum between the output and table[start][end] and update it into the output.
  3. Increase the value of x by 1.
4. Return table [start][end].

వివరణ

మేము ఒక సంఖ్య ఇచ్చాము n తద్వారా మన గెలుపుకు భరోసా ఇవ్వగలిగేంత డబ్బును మనం కనుగొనగలుగుతాము, దీని కోసం మనం ఒక సంఖ్యను and హించుకుని, ఆ సంఖ్యకు దిగువన మరియు ఆ సంఖ్యకు పైన కార్యకలాపాలను చేయవచ్చు. ఈ కోడ్ వెళ్తోంది పునరావృతంగా దాని విధులను కాల్ చేయండి.

సమస్య మిమ్మల్ని ఆశిస్తుంది గరిష్టాన్ని తగ్గించండి గెలవడానికి మీరు చెల్లించాల్సిన మొత్తం. వేరే అంచనా విషయంలో గెలవడానికి ఖచ్చితంగా వేరే ఖర్చు అవసరం, కాని 1… n మధ్య సంఖ్యను to హించడానికి అవసరమైన కనీస మొత్తాన్ని లెక్కించడం మా లక్ష్యం.

result = Math.min (ఫలితం, మొత్తం (i)) [అందించిన ఇన్‌పుట్‌ల యొక్క కనిష్టాన్ని అందిస్తుంది]

ఇక్కడ సంఖ్య (i) సంఖ్యను for హించడం కోసం చెత్త మొత్తం.

ఇప్పుడు, మీరు 3 ume హించినప్పుడు ఈ చెత్త కేసు ఏమిటి.

మీరు 1 ని ఎంచుకున్నారు, ఉత్తమ సందర్భంలో 1 మీరు to హించాల్సిన సంఖ్య కావచ్చు, అందువల్ల మొత్తం (i) = 0, కానీ మేము దాని గురించి బాధపడటం లేదు, మేము చెత్త కేసుతో బాధపడుతున్నాము, i, e 1 ఎంచుకున్న సంఖ్య కాదు. అందువల్ల 1 ఎంచుకున్నప్పుడు ఖర్చు = 1+ ఖర్చు (2,3).

మీరు 2 ని ఎంచుకున్నారు, ఉత్తమ సందర్భంలో 2 సమాధానం మరియు ఖర్చు 0, కానీ చెత్త సందర్భంలో 3 లేదా 1 గాని సమాధానం, మరియు ఒక సంఖ్యను on హించిన తర్వాత మీరు ఎంచుకున్న సంఖ్య ఎక్కువగా ఉందో లేదో తెలుసుకోండి లేదా సంఖ్య కంటే తక్కువ, అందువల్ల మనకు తెలుసు 1 సమాధానం లేదా 3 సమాధానం. అందువల్ల చెత్త కేసు 2.

3 చెత్త కేసును ఎంచుకోవడం (3) నుండి 1,2+ ఖర్చు అవుతుంది. తుది ఖర్చు ఈ చెత్త ఖర్చులన్నిటిలో కనిష్టంగా ఉంటుంది. సమాధానం పొందడానికి మరియు దానిని గుర్తుంచుకోవడానికి మేము దీన్ని పునరావృతంగా చేయాలి.

అమలు

గెస్ నంబర్ హయ్యర్ లేదా లోయర్ II సమస్య కోసం సి ++ ప్రోగ్రామ్

#include<iostream>
#include<vector>

using namespace std;

int helper(int low,int high,vector<vector<int>> &dp)
{
    if(low>=high)
        return 0;
    if(dp[low][high]!=INT_MAX)
        return dp[low][high];
    for(int j=low; j<=high; j++)
    {
        dp[low][high]=min(dp[low][high],max(j+helper(low,j-1,dp),j+helper(j+1,high,dp)));
    }
    return dp[low][high];

}
int getMoneyAmount(int n)
{
    vector<vector<int>> dp(n+1,vector<int>(n+1,INT_MAX));
    return helper(1,n,dp);
}

int main()
{
    cout<<getMoneyAmount(10);
}
16

గెస్ నంబర్ హయ్యర్ లేదా లోయర్ II సమస్య కోసం జావా ప్రోగ్రామ్

class guessNumber
{
    public static int getNumber(int n)
    {
        return guessNumberRec(new int[n+1][n+1], 1, n);
    }
    public static int guessNumberRec(int[][] arr, int left, int right)
    {
        if (left >= right)
        	return 0;
        if (arr[left][right] != 0)
        	return arr[left][right];

        arr[left][right] = Integer.MAX_VALUE;
        for (int a = left; a <= right; a++)
        {
            arr[left][right] = Math.min(arr[left][right], a + Math.max(guessNumberRec(arr, left, a - 1), guessNumberRec(arr, a + 1, right)));
        }
        return arr[left][right];
    }
    public static void main(String [] args)
    {
        System.out.println(getNumber(10));
    }
}
16

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై2) (ఇక్కడ  “N” ఎంచుకోగల సంఖ్యల పరిధి.

అంతరిక్ష సంక్లిష్టత

O (n లాగ్ n)  (ఇక్కడ  “N” ఎంచుకోగల సంఖ్యల పరిధి.