ਪਹਿਲੇ ਅਤੇ ਦੂਜੇ ਅੱਧ ਦੇ ਬਿੱਟਾਂ ਦੇ ਬਰਾਬਰ ਜੋੜ ਨਾਲ ਲੰਬਾਈ ਦੇ ਬਾਈਨਰੀ ਕ੍ਰਮ ਵੀ ਗਿਣੋ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ 24 * 7 ਇਨੋਵੇਸ਼ਨ ਲੈਬ ਐਮਾਜ਼ਾਨ ਡੈੱਲ GE ਹੈਲਥਕੇਅਰ
ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ

ਸਮੱਸਿਆ “ਪਹਿਲੇ ਅਤੇ ਦੂਜੇ ਅੱਧ ਦੇ ਬਿੱਟਾਂ ਦੇ ਬਰਾਬਰ ਜੋੜ ਨਾਲ ਲੰਬਾਈ ਦੇ ਬਾਈਨਰੀ ਕ੍ਰਮ ਵੀ ਗਿਣੋ” ਦੱਸਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਪੂਰਨ ਅੰਕ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ. ਹੁਣ ਅਕਾਰ 2 * n ਦੇ ਬਾਈਨਰੀ ਤਰਤੀਬ ਨੂੰ ਬਣਾਉਣ ਦੇ ਤਰੀਕਿਆਂ ਦੀ ਗਿਣਤੀ ਕਰੋ ਜਿਵੇਂ ਕਿ ਪਹਿਲੇ ਅੱਧ ਅਤੇ ਦੂਜੇ ਅੱਧ ਵਿਚ ਇਕੋ ਜਿਹੇ ਸਮੂਹ ਦੇ ਸੈੱਟ ਕੀਤੇ ਗਏ ਬਿੱਟ ਹਨ.

ਪਹਿਲੇ ਅਤੇ ਦੂਜੇ ਅੱਧ ਦੇ ਬਿੱਟਾਂ ਦੇ ਬਰਾਬਰ ਜੋੜ ਨਾਲ ਲੰਬਾਈ ਦੇ ਬਾਈਨਰੀ ਕ੍ਰਮ ਵੀ ਗਿਣੋ

ਉਦਾਹਰਨ

2
6

ਕਥਾ

ਬਾਈਨਰੀ ਲੜੀਵਾਰ 0000, 1001, 1010, 0110, 0101, 1111 ਹਨ. ਇਸ ਤਰ੍ਹਾਂ ਕੁੱਲ ਗਿਣਤੀ 1 ਹੈ.

ਪਹੁੰਚ

ਭੋਰਾ ਪਹੁੰਚ

ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਦਾ ਇਕ ਤਰੀਕਾ ਹੈ ਦੁਹਰਾਓ ਦੀ ਵਰਤੋਂ ਕਰਨਾ. ਇਸ ਲਈ, ਅਸੀਂ ਉਨ੍ਹਾਂ ਬਿੱਟਾਂ ਦੀ ਗਿਣਤੀ 'ਤੇ ਨਜ਼ਰ ਰੱਖਾਂਗੇ ਜੋ ਦੋਵਾਂ ਹਿੱਸਿਆਂ ਵਿਚ ਨਿਰਧਾਰਤ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਹੱਲ ਇਕ 3 ਰਾਜ ਹੱਲ ਹੈ. ਰਾਜ ਬਿੱਟਾਂ ਦੀ ਗਿਣਤੀ ਹੁੰਦੇ ਹਨ ਜਿਨ੍ਹਾਂ ਨੂੰ ਪਹਿਲੇ ਅੱਧ ਵਿੱਚ ਨਿਰਧਾਰਤ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੁੰਦੀ ਹੈ, ਦੂਜੇ ਅੱਧ ਵਿੱਚ ਨਿਰਧਾਰਤ ਕੀਤੇ ਜਾਣ ਵਾਲੇ ਬਿੱਟਾਂ ਦੀ ਗਿਣਤੀ, ਬਿਟਰੇਸ ਦੀ ਗਿਣਤੀ. ਹੇਠਾਂ ਦਿੱਤੇ ਕੋਡ ਵਿਚ ਦਿਖਾਇਆ ਗਿਆ ਇਕ ਆਮ ਆਵਰਤੀ ਹੱਲ ਵਰਗਾ ਦਿਖਾਈ ਦੇਵੇਗਾ.

#include <bits/stdc++.h>
using namespace std;

int n;
int rec(int a, int b, int i){
    if(i == n)
        if(a == 0 && b == 0)
            return 1;
        else
            return 0;
    return rec(a-1, b-1, i+1) + rec(a-1, b, i+1) + rec(a, b-1, i+1) + rec(a, b, i+1);
}

int main(){
    int t;cin>>t;
    while(t--){
        cin>>n;
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans += rec(i, i, 0);
        cout<<ans;
    }
}

ਹੱਲ ਵਧੀਆ ਹੈ ਪਰ ਬਹੁਤ ਅਸਮਰੱਥ ਹੈ. ਇਸ ਲਈ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ ਸੁਧਾਰਨ ਲਈ. ਅਸੀਂ ਵਰਤ ਸਕਦੇ ਹਾਂ ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ. ਪਰ ਫਿਰ ਵੀ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਤਿੰਨ ਰਾਜਾਂ ਦੇ ਕਾਰਨ O (N ^ 3) ਰਹੇਗੀ.

ਇਕ ਵਧੀਆ ਪਹੁੰਚ

ਆਕਸੀਵ ਫਾਰਮੂਲਾ ਅਤੇ ਵਰਤੋਂ ਨੂੰ ਬਦਲਣ ਬਾਰੇ ਸੋਚਣ ਲਈ ਇਕ ਬਿਹਤਰ ਪਹੁੰਚ ਹੋਵੇਗੀ ਗਤੀਸ਼ੀਲ ਪ੍ਰੋਗਰਾਮਿੰਗ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ. ਬਿੱਟ ਦੀ ਗਿਣਤੀ ਨੂੰ ਪਹਿਲੇ ਅਤੇ ਦੂਜੇ ਅੱਧ ਵਿਚ ਨਿਰਧਾਰਤ ਕਰਨ ਦੀ ਬਜਾਏ. ਅਸੀਂ ਫਰਕ ਦੀ ਵਰਤੋਂ ਕਰਦਿਆਂ ਦੋਵਾਂ ਰਾਜਾਂ ਨੂੰ ਇੱਕ ਰਾਜ ਵਿੱਚ ਘਟਾ ਸਕਦੇ ਹਾਂ. ਹੁਣ ਸਾਡਾ ਰਿਕਰਸਿਵ ਫਾਰਮੂਲਾ ਬਦਲ ਗਿਆ ਹੈ ਅਤੇ ਇਸ ਲਈ ਸਾਡੀ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਅਤੇ ਸਪੇਸ ਦੀ ਗੁੰਝਲਤਾ. ਅਸੀਂ ਇੱਕ ਹੱਲ ਲਿਖ ਸਕਦੇ ਹਾਂ ਜੋ ਓ (ਐਨ ^ 2) ਸਮੇਂ ਵਿੱਚ ਚੱਲ ਸਕਦਾ ਹੈ.

ਪਹਿਲੇ ਅਤੇ ਦੂਜੇ ਅੱਧ ਦੇ ਬਿੱਟਾਂ ਦੇ ਬਰਾਬਰ ਜੋੜ ਦੇ ਨਾਲ ਲੰਬਾਈ ਦੇ ਬਾਈਨਰੀ ਕ੍ਰਮ ਨੂੰ ਗਿਣਨਾ ਸੀ ++ ਕੋਡ

#include <bits/stdc++.h>
using namespace std;

int n;
int rec(int diff, int i, vector<vector<int>> &dp){
    if(i == n)
        if(diff == 0)
            return 1;
        else
            return 0;
    if(dp[diff+n][i] != -1)
        return dp[diff+n][i];
    return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
}

int main(){
    cin>>n;
    vector<vector<int>> dp(2*n+2, vector<int>(n+1, -1));
    int ans = rec(0, 0, dp);
    cout<<ans;
}
6
924

ਪਹਿਲੇ ਅਤੇ ਦੂਜੇ ਅੱਧ ਦੇ ਬਿੱਟਾਂ ਦੇ ਬਰਾਬਰ ਜੋੜ ਨਾਲ ਲੰਬਾਈ ਦੇ ਬਾਈਨਰੀ ਕ੍ਰਮ ਨੂੰ ਗਿਣਨ ਲਈ ਜਾਵਾ ਕੋਡ

import java.util.*;

class Main{
  static int n;
  static int rec(int diff, int i, int dp[][]){
      if(i == n)
          if(diff == 0)
              return 1;
          else
              return 0;
      if(dp[diff+n][i] != -1)
          return dp[diff+n][i];
      return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
  }
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
      n = sc.nextInt();
      int dp[][] = new int[2*n+2][n+1];
      for(int i=0;i<2*n+2;i++){
      	for(int j=0;j<n+1;j++)
      		dp[i][j] = -1;
      }
      int ans = rec(0, 0, dp);
      System.out.print(ans);
  }
}
6
924

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ ^ 2), ਕਿਉਂਕਿ ਸਮੱਸਿਆ ਵਿੱਚ ਐਨ ^ 2 ਵੱਖਰੇ ਰਾਜ ਸਨ. ਇਸ ਪ੍ਰਕਾਰ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਬਹੁਪੱਖੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ ^ 2), ਕਿਉਂਕਿ ਅਸੀਂ ਇੱਕ 2D ਡੀਪੀ ਐਰੇ ਬਣਾਇਆ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਪੁਲਾੜ ਦੀ ਜਟਿਲਤਾ ਵੀ ਬਹੁਪੱਖੀ ਹੈ.

ਵਧੀਆ ਪਹੁੰਚ

ਬਿਹਤਰ ਪਹੁੰਚ ਸਮੱਸਿਆ ਦੇ ਉੱਤਰ ਦੀ ਗਣਨਾ ਕਰਨ ਲਈ ਬਿਨੋਮਿਅਲ ਗੁਣਾਂਕ ਦੀ ਵਰਤੋਂ ਕਰਨਾ ਹੈ. ਅਸੀਂ ਦੋਹਾਂ ਹਿੱਸਿਆਂ ਨੂੰ ਸੁਤੰਤਰ ਮੰਨ ਸਕਦੇ ਹਾਂ. ਫਿਰ ਜੇ ਉਹ ਸੁਤੰਤਰ ਹਨ ਅਤੇ ਸਾਨੂੰ ਬਸ ਕੁਝ ਬਿੱਟ ਸੈਟ ਕਰਨੇ ਪੈਣਗੇ. ਵਿਚਾਰ ਕਰੋ ਸਾਨੂੰ n ਬਿੱਟ ਤੋਂ ਬਾਹਰ ਕੇ ਬਿੱਟ ਸੈਟ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਤਾਂ ਅਸੀ ਅਸਾਨ ਤਰੀਕੇ ਨਾਲ ਇਹ ਲਿਖ ਸਕਦੇ ਹਾਂ ਕਿ ਇਹ ਐਨ ਸੀ ਕੇ * ਐਨ ਸੀ ਕੇ ਦੇ ਬਰਾਬਰ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਜੇ ਅਸੀਂ ਇਸ ਵੈਲਯੂ ਨੂੰ k ਦੇ ਬਰਾਬਰ 0 ਤੋਂ k ਦੇ ਬਰਾਬਰ n ਦੀ ਗਣਨਾ ਕਰਦੇ ਹਾਂ. ਸਾਨੂੰ ਜਵਾਬ ਮਿਲ ਗਿਆ ਹੁੰਦਾ.

ਪਹਿਲੇ ਅਤੇ ਦੂਜੇ ਅੱਧ ਦੇ ਬਿੱਟਾਂ ਦੇ ਬਰਾਬਰ ਜੋੜ ਦੇ ਨਾਲ ਲੰਬਾਈ ਦੇ ਬਾਈਨਰੀ ਕ੍ਰਮ ਨੂੰ ਗਿਣਨਾ ਸੀ ++ ਕੋਡ

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;cin>>n;
    int C = 1, answer = 1;
    for (int i = 1; i<=n ; i++)
    {
        C = (C * (n+1-i))/i;
        answer += (C*C);
    }
    cout<<answer;
}
6
924

ਪਹਿਲੇ ਅਤੇ ਦੂਜੇ ਅੱਧ ਦੇ ਬਿੱਟਾਂ ਦੇ ਬਰਾਬਰ ਜੋੜ ਨਾਲ ਲੰਬਾਈ ਦੇ ਬਾਈਨਰੀ ਕ੍ਰਮ ਨੂੰ ਗਿਣਨ ਲਈ ਜਾਵਾ ਕੋਡ

import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int answer = 1, C = 1;
      for(int i = 1; i<=n; i++)
      {
          C = (C * (n+1-i))/i;
          answer += (C*C);
      }
      System.out.print(answer);
  }
}
6
924

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ ਐਨ ਤਕ ਇਕੋ ਲੂਪ ਚਲਾਇਆ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਐਲਗੋਰਿਦਮ ਵਿਚ ਲੰਬੇ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1), ਕਿਉਂਕਿ ਸਪੇਸ ਦੀ ਗੁੰਝਲਤਾ ਨਿਰੰਤਰ ਹੈ.