N-th ട്രിബൊനാച്ചി നമ്പർ ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ഫേസ്ബുക്ക്
ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

പ്രശ്നം പ്രസ്താവന

”N-th ട്രിബൊനാച്ചി നമ്പർ” എന്ന പ്രശ്‌നത്തിൽ ഞങ്ങൾക്ക് ഒരു നമ്പർ നൽകിയിരിക്കുന്നു. N-th കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല ട്രിബൊനാച്ചി സംഖ്യ.

സീറോത്ത് ട്രിബൊനാച്ചി നമ്പർ 0. ആദ്യത്തെ ട്രിബൊനാച്ചി നമ്പർ 1. രണ്ടാമത്തെ ട്രിബൊനാച്ചി നമ്പർ 1 ആണ്.

(N-1- ട്രിബൊനാച്ചി നമ്പർ), (N-2- ട്രിബൊനാച്ചി നമ്പർ), (N-3- ട്രിബൊനാച്ചി നമ്പർ) എന്നിവയുടെ സംഗ്രഹമാണ് N-th ട്രിബൊനാച്ചി നമ്പർ.

N-th ട്രിബൊനാച്ചി നമ്പർ ലീറ്റ്കോഡ് പരിഹാരം

ഉദാഹരണം

n = 4
4

വിശദീകരണം: പൂജ്യമെന്ന നിലയിൽ, ഒന്നും രണ്ടും ട്രിബൊനാച്ചി സംഖ്യകൾ യഥാക്രമം 0,1,1 ആണ്. അതിനാൽ മൂന്നാമത്തെ ട്രിബൊനാച്ചി നമ്പർ (0 + 1 + 1) 2. അതുപോലെ, നാലാമത്തെ ട്രിബൊനാച്ചി (1 + 1 + 2) 4 ആണ്.

N-th ട്രിബൊനാച്ചി നമ്പർ ലീറ്റ്കോഡ് പരിഹാരത്തിനുള്ള സമീപനം

N-th ട്രിബൊനാച്ചി സംഖ്യയെ (N-1), (N-2), (N-3) ട്രിബൊനാച്ചി സംഖ്യകളുടെ സംഗ്രഹമായി നിർവചിച്ചിരിക്കുന്നു. അതിനാൽ നമുക്ക് ആദ്യം (N-3) -th ട്രിബൊനാച്ചി നമ്പർ ആവശ്യമാണ് (N-2), (N-1), (N) -th ട്രിബൊനാച്ചി നമ്പർ എന്നിവ കണക്കാക്കാൻ ഇത് ഉപയോഗിക്കും. (N-3) -th ട്രിബൊനാച്ചി നമ്പർ കണക്കാക്കലാണ് ഇപ്പോൾ ഞങ്ങളുടെ പുതിയ പ്രശ്നം. ഇവിടെ നമുക്ക് ഒരു കാര്യം നിഗമനം ചെയ്യാം, അതായത് ഒൻപതാം ട്രിബൊനാച്ചി നമ്പർ കണക്കാക്കേണ്ടതുണ്ട്, കാരണം ഓരോ അടുത്ത മൂല്യവും മുമ്പത്തെ മൂന്ന് മൂല്യങ്ങളെ ആശ്രയിച്ചിരിക്കുന്നു. ഞങ്ങൾ ഈ ഘട്ടങ്ങൾ പാലിക്കും:

  1. പൂജ്യം, ഒന്നും രണ്ടും ട്രിബൊനാച്ചി സംഖ്യകളുടെ മൂല്യങ്ങൾ യഥാക്രമം a, b, c എന്നിങ്ങനെ മൂന്ന് വേരിയബിളുകളിൽ സൂക്ഷിക്കും.
  2. ഇവിടെ a, b, c എന്നിവ അവസാനത്തെ മൂന്ന് ട്രിബൊനാച്ചി നമ്പറുകൾ സംഭരിക്കും. ഈ അവസാന മൂന്ന് ട്രിബൊനാച്ചി നമ്പറുകൾ ഉപയോഗിച്ച് ഞങ്ങൾ അടുത്ത ട്രിബൊനാച്ചി നമ്പർ കണക്കാക്കുകയും എ, ബി, സി എന്നിവയുടെ മൂല്യങ്ങൾ അപ്‌ഡേറ്റ് ചെയ്യുകയും ചെയ്യും.
  3. N-th ട്രിബൊനാച്ചി നമ്പറിന്റെ മൂല്യം കണ്ടെത്തുന്നതുവരെ ഞങ്ങൾ ഘട്ടം -2 ആവർത്തിക്കും, തുടർന്ന് ഞങ്ങൾ അത് തിരികെ നൽകും.

നടപ്പിലാക്കൽ

N-th ട്രിബൊനാച്ചി നമ്പറിനായുള്ള C ++ കോഡ്

#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-th ട്രിബൊനാച്ചി നമ്പർ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

മുകളിലുള്ള കോഡിന്റെ സമയ സങ്കീർണ്ണതയാണ് O (n) കാരണം ഞങ്ങൾ N-th ട്രിബൊനാച്ചി നമ്പർ വരെ ആവർത്തിക്കുന്നു. ഇവിടെ n എന്നത് തന്നിരിക്കുന്ന നമ്പറാണ്, അതിനായി N-th ട്രിബൊനാച്ചി നമ്പർ കണക്കാക്കേണ്ടതുണ്ട്.

സ്ഥല സങ്കീർണ്ണത

മുകളിലുള്ള കോഡിന്റെ സ്ഥല സങ്കീർണ്ണത O (1) കാരണം ഉത്തരം സംഭരിക്കാൻ ഞങ്ങൾ ഒരു വേരിയബിൾ മാത്രമാണ് ഉപയോഗിക്കുന്നത്.

അവലംബം