एन-थ्री ट्रीबोनाकी नंबर लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले फेसबुक
डायनॅमिक प्रोग्रामिंग

समस्या विधान

"एन-थ्री ट्रीबोनाकी नंबर" या समस्येमध्ये आम्हाला एक एन दिलेला आहे. आमचे कार्य एन-व्या शोधणे आहे ट्रिबोनॅकी संख्या

झिरोथ ट्रिबोनॅची संख्या ० आहे. प्रथम ट्रायबोनॅकी क्रमांक १ आहे. दुसरी ट्रायबोनॅकी क्रमांक १ आहे.

एन-थ्री ट्रीबोनासी नंबर (एन -1- व्या ट्रायबोनॅकी नंबर), (एन -2-व्या ट्रायबोनॅकी नंबर) आणि (एन -3-थ्री ट्रोबोनॅकी नंबर) यांचा योग आहे.

एन-थ्री ट्रीबोनाकी नंबर लीटकोड सोल्यूशन

उदाहरण

n = 4
4

स्पष्टीकरण: शून्य म्हणून, प्रथम आणि द्वितीय ट्रायबोनॅकी क्रमांक अनुक्रमे 0,1,1 आहेत. तर तिसरा ट्रिबोनॅसी नंबर (० + १ + १) २ आहे. त्याचप्रमाणे, चौथा ट्रिबोनॅसी (१ + १ + २). आहे.

एन-थ्री ट्रीबोनाकी नंबर लीटकोड सोल्यूशनसाठी दृष्टीकोन

एन-थ्री ट्रीबोनासी नंबरची व्याख्या (एन -१), (एन -२), आणि (एन-1) ट्रिबोनॅकी नंबरची बेरीज म्हणून केली जाते. म्हणून आम्हाला प्रथम (एन -2) -वा ट्रायबोनॅकी नंबर हवा आहे जो हा गणना करण्यासाठी (एन -3), (एन -3) आणि (एन)-व्या ट्रीबोनॅकी नंबरमध्ये वापरला जाईल. तर आता आमची नवीन समस्या म्हणजे (एन -2) -thth ट्रीबोनॅकी नंबरची गणना करणे आहे. येथे आपण एक गोष्ट सांगू शकतो की एन-थ्री ट्रिबोनॅसी नंबरची गणना करण्यासाठी आम्हाला एन-थ ट्रिबोनॅसी नंबरची गणना करणे आवश्यक आहे कारण प्रत्येक पुढील मूल्य मागील तीन मूल्यांवर अवलंबून असते. आम्ही या चरणांचे अनुसरण करू:

  1. आम्ही शून्य, प्रथम आणि द्वितीय ट्रायबोनॅकी क्रमांकांची मूल्ये अनुक्रमे ए, बी आणि सी तीन व्हेरिएबल्समध्ये संचित करू.
  2. येथे a, b आणि c शेवटच्या तीन ट्रिबोनॅकी नंबर संचित करेल. या शेवटच्या तीन ट्रीबोनॅकी नंबरचा वापर करून आपण पुढील ट्रिबोनॅकी नंबरची गणना करू आणि नंतर अ, बी आणि सी ची व्हॅल्यूज अपडेट करू.
  3. आम्ही एन-व्या ट्रायबोनॅकी क्रमांकाचे मूल्य शोधत नाही तोपर्यंत आम्ही चरण -2 ची पुनरावृत्ती करू आणि आम्ही ते परत करू.

अंमलबजावणी

एन-व्या ट्रीबोनॅकी नंबरसाठी सी ++ कोड

#include <bits/stdc++.h> 
using namespace std; 
    int tribonacci(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 1, d = a + b + c;
        while (n-- > 2) {
            d = a + b + c, a = b, b = c, c = d;
        }
        return c;
    }

int main() 
{ 
int n=4;
int ans=tribonacci(n); 
 cout<<ans<<endl;
 return 0;
}
4

एन-थ ट्रिबोनॅसी नंबरसाठी जावा कोड

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static int tribonacci(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 1, d;
        while (n-- > 2) {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return c;
    }
  public static void main(String[] args) {
        int n=4; 
        int ans=tribonacci(n); 
        System.out.println(ans);
  }
}
4

एन-थ ट्रिबोनॅसी नंबर लीटकोड सोल्यूशनचे जटिल विश्लेषण

वेळ गुंतागुंत

वरील कोडची वेळ जटिलता आहे O (n) कारण आम्ही एन-थ्री ट्रिबोनॅकी नंबरपर्यंत पुनरावृत्ती करत आहोत. येथे एन दिलेली संख्या आहे ज्यासाठी आम्हाला एन-व्या ट्रीबोनॅकी नंबरची गणना करणे आवश्यक आहे.

जागेची जटिलता

वरील कोडची स्पेस कॉम्प्लेक्सिटी आहे ओ (1) कारण आम्ही उत्तर संग्रहित करण्यासाठी फक्त एक व्हेरिएबल वापरत आहोत.

संदर्भ