এন-থ্রি ট্রাইবোনচি নম্বর লেটকোড সমাধান  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় ফেসবুক
আলগোরিদিম আইনসংগ্রহ ডায়নামিক প্রোগ্রামিং সাক্ষাত্কার সাক্ষাৎকারের প্রস্তুতি লেটকোড LeetCodeSolutions

সমস্যা বিবৃতি  

"N-th Tribonacci সংখ্যা" সমস্যাটিতে আমাদের একটি নম্বর দেওয়া হয়। আমাদের কাজটি N-th খুঁজে বের করা ট্রাইবোনসি সংখ্যা।

জেরোথ ট্রাইবোনাকি সংখ্যাটি ০. প্রথম ট্রাইবোনাকি নম্বরটি ১ The দ্বিতীয় ট্রাইবোনাকি সংখ্যাটি।।

এন-ত্রি ট্রাইবোনাকি সংখ্যাটি হ'ল (এন -১- ত্রি ট্রাইবোনাকি সংখ্যা), (এন -২- ত্রি ট্রাইবোনাকি সংখ্যা) এবং (এন-তৃতীয় ত্রিভোনাচি সংখ্যা)।

এন-থ্রি ট্রাইবোনচি নম্বর লেটকোড সমাধানপিন

উদাহরণ

n = 4
4

ব্যাখ্যা: জেরোথ হিসাবে, প্রথম এবং দ্বিতীয় ট্রাইবোনাকি সংখ্যা যথাক্রমে 0,1,1। সুতরাং তৃতীয় ট্রাইবোনাকি সংখ্যাটি (0 + 1 + 1) ২. একইভাবে, চতুর্থ ট্রাইবোনাকি (2 + 1 + 1) 2।

এন-থ্রি ট্রাইবোনাকি নম্বর লেটকোড সমাধানের জন্য পদ্ধতির Appro  

যেহেতু এন-ত্রি ট্রাইবোনচি নম্বরটি সংশ্লেষ হিসাবে সংযুক্ত করা হয় (এন -১), (এন -২), এবং (এন -৩) ট্রাইবোনাকি সংখ্যা number সুতরাং আমাদের প্রথমে (N-1) -th ত্রিভোনাচি নম্বরটি প্রয়োজন এটি গণনা করতে ব্যবহৃত হবে (N-2), (N-3), এবং (N) -th ত্রিবোনাকি নম্বর। সুতরাং এখন আমাদের নতুন সমস্যাটি হ'ল (এন -৩)-তম ট্রাইবোনাকি নম্বর গণনা করা। এখানে আমরা একটি জিনিস উপসংহারে পৌঁছাতে পারি যে এন-ত্রি ট্রাইবোনচি নম্বরটি গণনা করার জন্য আমাদের একটিকে এন-ত্রি ট্রাইবোনাকী নম্বর গণনা করতে হবে কারণ প্রতিটি পরবর্তী মান পূর্ববর্তী তিনটি মানের উপর নির্ভরশীল। আমরা এই পদক্ষেপগুলি অনুসরণ করব:

  1. আমরা যথাক্রমে ক, খ এবং সি তিনটি ভেরিয়েবেলে জেরোথ, প্রথম এবং দ্বিতীয় ট্রাইবোনাকির সংখ্যার মান সংরক্ষণ করব।
  2. এখানে a, b এবং c শেষ তিনটি ট্রাইবোনাকি নম্বর সংরক্ষণ করবে। এই শেষ তিনটি ট্রাইবোনাকি নম্বর ব্যবহার করে আমরা পরবর্তী ট্রাইবোনাকি নম্বর গণনা করব এবং তারপরে a, b, এবং c এর মান আপডেট করব।
  3. আমরা ধাপ -২ পুনরুক্তি করব যতক্ষণ না আমরা N-th ট্রাইবোনচি নম্বরটির মান খুঁজে পাই তবে আমরা এটি ফিরিয়ে দেব।
আরো দেখুন
সাজানো অ্যারে লেটকোড সমাধানে এলিমেন্টের প্রথম এবং শেষ অবস্থান সন্ধান করুন

বাস্তবায়ন

সি -+ এন-থ্রি ট্রাইবোনাকি নম্বরটির কোড

#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

N-th ট্রাইবোনাকি নম্বরটির জন্য জাভা কোড

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

এন-থ্রি ট্রাইবোনাকি নম্বর লেটকোড সমাধানের জটিলতা বিশ্লেষণ  

সময়ের জটিলতা

উপরের কোডটির সময় জটিলতা উপর) কারণ আমরা এন-থ্রি ট্রাইবোনাকি নম্বর পর্যন্ত পুনরাবৃত্তি করছি। এখানে n হল প্রদত্ত নম্বর যার জন্য আমাদের N-th ট্রাইবোনাকি নম্বর গণনা করা প্রয়োজন।

স্থান জটিলতা

উপরের কোডটির স্পেস জটিলতা ও (1) কারণ আমরা উত্তর সংরক্ষণের জন্য কেবল একটি পরিবর্তনশীল ব্যবহার করছি।

তথ্যসূত্র