ಮೊಬೈಲ್ ಸಂಖ್ಯಾ ಕೀಪ್ಯಾಡ್ ಸಮಸ್ಯೆ


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ MAQ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಸ್ಪ್ರಿಂಕ್ಲರ್
ಸಂಯೋಜನೆ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಸ್ಟ್ರಿಂಗ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ಮೊಬೈಲ್ ಸಂಖ್ಯಾ ಕೀಪ್ಯಾಡ್ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಾವು ಸಂಖ್ಯಾ ಕೀಪ್ಯಾಡ್ ಅನ್ನು ಪರಿಗಣಿಸುತ್ತೇವೆ. ಪ್ರಸ್ತುತ ಬಟನ್‌ನ ಮೇಲಿನ, ಕೆಳ, ಎಡ ಮತ್ತು ಬಲ ಗುಂಡಿಗಳನ್ನು ಒತ್ತುವಂತೆ ಮಾತ್ರ ನಿಮಗೆ ಅನುಮತಿಸಲಾದ ನಿರ್ದಿಷ್ಟ ಉದ್ದದ ಎಲ್ಲಾ ಸಂಖ್ಯಾ ಅನುಕ್ರಮಗಳನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ. ಕೆಳಗಿನ ಚಿತ್ರದಲ್ಲಿ ಬೂದು ಎಂದು ಗುರುತಿಸಲಾದ ಕೆಳಗಿನ ಸಾಲು ಮೂಲೆಯ ಗುಂಡಿಗಳನ್ನು (* (ನಕ್ಷತ್ರ) ಮತ್ತು # (ಹ್ಯಾಶ್)) ಒತ್ತಿ ನಿಮಗೆ ಅನುಮತಿಸಲಾಗುವುದಿಲ್ಲ.

ಸಂಖ್ಯಾ ಕೀಪ್ಯಾಡ್

ಉದಾಹರಣೆ

1
10

ವಿವರಣೆ: ನೀವು ಎಲ್ಲಾ ಅಂಕೆಗಳನ್ನು (0 ರಿಂದ 9) ಬಳಸಬಹುದು, ಹೀಗಾಗಿ ಉತ್ತರಕ್ಕೆ 10 ಕೊಡುಗೆ ನೀಡುತ್ತದೆ.

2
36

ವಿವರಣೆ: ನೀವು 0 ಅನ್ನು ಆರಿಸುವುದನ್ನು ಪರಿಗಣಿಸಿ, ನಂತರ ನೀವು 0 ಮತ್ತು 8 ಅನ್ನು ಎರಡನೇ ಸಂಖ್ಯೆಯಾಗಿ ಆಯ್ಕೆ ಮಾಡಬಹುದು.

ನೀವು 1 ಅನ್ನು ಆರಿಸಿಕೊಳ್ಳಿ, ನಂತರ ನೀವು 1, 2, 4 ಅನ್ನು ಎರಡನೇ ಸಂಖ್ಯೆಯಾಗಿ ಆಯ್ಕೆ ಮಾಡಬಹುದು. ಅಂತೆಯೇ, ನಾವು ಇದನ್ನು ಎಲ್ಲಾ ಅಂಕೆಗಳಿಗೆ ಮಾಡುತ್ತೇವೆ.

 

ಮೊಬೈಲ್ ಸಂಖ್ಯಾ ಕೀಪ್ಯಾಡ್ ಸಮಸ್ಯೆಯ ವಿಧಾನ

ಪುನರಾವರ್ತಿತ ಅಪ್ರೋಚ್

ಮೊಬೈಲ್ ಸಂಖ್ಯಾ ಕೀಪ್ಯಾಡ್ ಸಮಸ್ಯೆಗೆ, ಮನಸ್ಸಿಗೆ ಬರುವ ಮೊದಲ ವಿಷಯವೆಂದರೆ ಪುನರಾವರ್ತಿತ ವಿಧಾನ. ಆದ್ದರಿಂದ, ನಾವು ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಬಹುದು ಪುನರಾವರ್ತಿತವಾಗಿ ಅಂದರೆ ನಾವು i, j ಸ್ಥಾನದಲ್ಲಿದ್ದರೆ ಮತ್ತು ನಾವು ಆಯ್ಕೆ ಮಾಡಲು n ಸಂಖ್ಯೆಗಳನ್ನು ಹೊಂದಿದ್ದರೆ ನಾವು ಮೇಲ್ಮುಖ ದಿಕ್ಕಿನಲ್ಲಿ (i-1, j), ಕೆಳಮುಖ ದಿಕ್ಕಿನಲ್ಲಿ (i + 1, j), ಎಡ ದಿಕ್ಕಿನಲ್ಲಿ (i, j-1 ), ಸರಿಯಾದ ದಿಕ್ಕು (i, j + 1) ಮತ್ತು ಈಗ ಆಯ್ಕೆ ಮಾಡಲು n-1 ಸಂಖ್ಯೆಗಳೊಂದಿಗೆ ಪ್ರಸ್ತುತ ಸ್ಥಾನದಲ್ಲಿ (i, j) ಇರಿ. ಈ ವಿಧಾನವು ಸಂಪೂರ್ಣವಾಗಿ ಸರಿ ಆದರೆ ಸಾಕಷ್ಟು ಪರಿಣಾಮಕಾರಿಯಾಗಿಲ್ಲ.

//Base Case
if (N = 1) return 10
else
    return sum of all findNumberOfSequences(i, j, n) where i,j is new position after a valid move from current position

ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್

ನಾವು n ಗೆ ಸಮನಾದ ಸಂಖ್ಯೆಯ ಅನುಕ್ರಮದ ಉದ್ದಕ್ಕಾಗಿ ಮೊಬೈಲ್ ಸಂಖ್ಯಾ ಕೀಪ್ಯಾಡ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಪ್ರಯತ್ನಿಸಿದಾಗ. ಆರಂಭಿಕ ಸಮಸ್ಯೆ ಸಣ್ಣ ಉಪ-ಸಮಸ್ಯೆಗಳ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿದೆ ಎಂದು ನಾವು ನೋಡಬಹುದು. ನಾವು n ಗೆ 3 ಕ್ಕೆ ಸಮನಾಗಿ ಪರಿಹರಿಸುವಾಗ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಗಣಿಸಿ. ನಂತರ ನಮ್ಮ ಸಮಸ್ಯೆ 2 ಕ್ಕೆ ಸಮನಾದ ಉದ್ದದ ಅನುಕ್ರಮಗಳ ಸಂಖ್ಯೆಯನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ ಎಂದು ನಾವು ನೋಡಬಹುದು. ನಂತರ ನಾವು ಮೇಲ್ಮುಖವಾಗಿ ಕೆಳ ದಿಕ್ಕಿಗೆ ಎಡ ದಿಕ್ಕಿಗೆ ಮತ್ತು ಬಲ ದಿಕ್ಕಿನಲ್ಲಿ ಚಲಿಸುತ್ತೇವೆ ಅಥವಾ ಉಳಿಯುತ್ತೇವೆ ಅದೇ ಸ್ಥಳ ಆದರೆ ನಾವು ಈ ಸ್ಥಾನವನ್ನು (ಅಂಕೆ) ತೆಗೆದುಕೊಂಡು ಉತ್ತರಿಸಲು ಸೇರಿಸಿದಾಗಿನಿಂದ. ಸಮಸ್ಯೆಯನ್ನು n = 2 ರೊಂದಿಗಿನ ಸಣ್ಣ ಸಮಸ್ಯೆಗೆ ಇಳಿಸಲಾಗಿದೆ. ಈಗ ನಾವು ಒಂದು ಅಂಕಿಯಿಂದ ಪ್ರಾರಂಭಿಸಿ ಅನುಮತಿಸಲಾದ ದಿಕ್ಕುಗಳಲ್ಲಿ ಚಲಿಸಿದ್ದೇವೆ ಎಂದು ನೋಡಿದರೆ, ನಾವು ಸಬ್‌ಪ್ರೊಬ್ಲೆಮ್‌ಗಳನ್ನು ಅತಿಕ್ರಮಿಸುತ್ತಿರುವುದನ್ನು ನಾವು ನೋಡಬಹುದು ಆದ್ದರಿಂದ ಇದು ನಮಗೆ ಬಳಸುವ ಅಂತಃಪ್ರಜ್ಞೆಯನ್ನು ನೀಡುತ್ತದೆ ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್.

ಸಾಮಾನ್ಯವಾಗಿ ಸೈನ್ ಇನ್ ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್, ನಾವು ಏನು ಮಾಡಬೇಕೆಂದರೆ ನಾವು ಮೊದಲು ಸಣ್ಣ ಸಮಸ್ಯೆಗಳಿಗೆ ಪರಿಹರಿಸುತ್ತೇವೆ ಮತ್ತು ನಂತರ ನಮ್ಮ ಆರಂಭಿಕ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಸಣ್ಣ ಸಮಸ್ಯೆಗಳ ಫಲಿತಾಂಶಗಳನ್ನು ಸಂಯೋಜಿಸುತ್ತೇವೆ ಆದ್ದರಿಂದ ಏನು ಮಾಡಲಾಗುವುದು n ಗೆ 1 ಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ ಮತ್ತು n 2 ಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ, ಮತ್ತು ಹೀಗೆ.

ಕೋಡ್

ಸಿ ++ ಕೋಡ್

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

int findNumberOfSequences(int n) 
{ 
  char keypad[4][3] = {{'1','2','3'}, 
                       {'4','5','6'}, 
                       {'7','8','9'}, 
                       {'*','0','#'}};
  
  //Base Case
  if(n <= 0) 
    return 0; 
  if(n == 1) 
    return 10; 

  //Directions to move to
  int dir[][2]= {{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}};

  //dp[i][j] = number of sequences of length j starting with digit i
  int dp[10][n+1];
  memset(dp,0, sizeof dp);
  
  // fill the numbers starting with digit i and of length 1 
  for(int i=0; i<=9; i++)
    dp[i][1] = 1;

  // Now solve problem for n=2,3,.. using smaller sub-problems
  for(int sizeOfSequence=2; sizeOfSequence<=n; sizeOfSequence++)
  { 
    for(int row=0; row<4; row++)
    { 
      for (int col=0; col<3; col++)
      { 
        if (keypad[row][col] != '*' && keypad[row][col] != '#') 
        { 
          //fixing the first digit
          int num = keypad[row][col] - '0';

          //Now select the remaining digit in sequence
          for(int step=0; step<5; step++) 
          { 
            int new_row = row + dir[step][0]; 
            int new_col = col + dir[step][1]; 
            if(new_row>=0 && new_row<4 && new_col>=0 && new_col<3
            && keypad[new_row][new_col]!='*' && keypad[new_row][new_col]!='#') 
            { 
              int nextNum = keypad[new_row][new_col] - '0'; 
              dp[num][sizeOfSequence] += dp[nextNum][sizeOfSequence-1]; 
            } 
          } 
        } 
      } 
    } 
  } 

  // Add the number of sequences of length starting with digit i(0 to 9)
  int ans = 0; 
  for(int i=0; i<=9; i++) 
    ans += dp[i][n]; 
  return ans; 
} 

int main() 
{ 
  int t;cin>>t;
  while(t--){
    int n;cin>>n;
    cout<<"Number of sequences of length "<<n<<" = "<<findNumberOfSequences(n)<<endl;
  }
} 
5
1
2
3
4
5
Number of sequences of length 1 = 10
Number of sequences of length 2 = 36 
Number of sequences of length 3 = 138 
Number of sequences of length 4 = 532 
Number of sequences of length 5 = 2062

 

ಜಾವಾ ಕೋಡ್

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    
    static int findNumberOfSequences(int n) 
    { 
      	char keypad[][] = {{'1','2','3'}, 
    		           {'4','5','6'}, 
    	         	   {'7','8','9'}, 
    			   {'*','0','#'}};
      
      	//Base Case
    	if(n <= 0) 
    		return 0; 
    	if(n == 1) 
    		return 10; 
    
    	//Directions to move to
    	int dir[][]= {{0,0}, {0,-1}, {-1,0}, {0,1}, {1,0}};
    
    	//dp[i][j] = number of sequences of length j starting with digit i
    	int dp[][] = new int[10][n+1];
        
        for(int i=0;i<10;i++)
            for(int j=0;j<n+1;j++)
                dp[i][j]= 0;
                
    	// fill the numbers starting with digit i and of length 1 
    	for(int i=0; i<=9; i++)
    		dp[i][1] = 1;
    
    	// Now solve problem for n=2,3,.. using smaller sub-problems
    	for(int sizeOfSequence=2; sizeOfSequence<=n; sizeOfSequence++)
    	{ 
    		for(int row=0; row<4; row++)
    		{ 
    			for (int col=0; col<3; col++)
    			{ 
    				if (keypad[row][col] != '*' && keypad[row][col] != '#') 
    				{ 
    					//fixing the first digit
    					int num = keypad[row][col] - '0';
    
    					//Now select the remaining digit in sequence
    					for(int step=0; step<5; step++) 
    					{ 
    						int new_row = row + dir[step][0]; 
    						int new_col = col + dir[step][1]; 
    						if(new_row>=0 && new_row<4 && new_col>=0 && new_col<3
                                                && keypad[new_row][new_col]!='*' && keypad[new_row][new_col]!='#') 
    						{ 
    							int nextNum = keypad[new_row][new_col] - '0'; 
    							dp[num][sizeOfSequence] += dp[nextNum][sizeOfSequence-1]; 
    						} 
    					} 
    				} 
    			} 
    		} 
    	} 
    
      	// Add the number of sequences of length starting with digit i(0 to 9)
    	int ans = 0; 
    	for(int i=0; i<=9; i++) 
    		ans += dp[i][n]; 
    	return ans; 
    } 

    public static void main(String[] args) 
    { 
        
    	Scanner sc = new Scanner(System.in); 
    	int t = sc.nextInt(); 
    	while(t-- > 0){ 
            int n = sc.nextInt();
            int ans = findNumberOfSequences(n);
    	    System.out.println("Number of sequences of length "+n+" = "+ans);
    	}
    } 
}
5
1
2
3
4
5
Number of sequences of length 1 = 10
Number of sequences of length 2 = 36
Number of sequences of length 3 = 138
Number of sequences of length 4 = 532
Number of sequences of length 5 = 2062

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ: ಮೊಬೈಲ್ ಸಂಖ್ಯಾ ಕೀಪ್ಯಾಡ್ ಸಮಸ್ಯೆಗೆ ಒ (ಎನ್)

ನಾವು ಅನೇಕ ನೆಸ್ಟೆಡ್ ಲೂಪ್‌ಗಳನ್ನು ಬಳಸಿದ್ದರೂ ಸಹ ಅವುಗಳನ್ನು ಸ್ಥಿರ ಸಮಯದಲ್ಲಿ ಚಲಿಸುವಂತೆ ನಾವು ಪರಿಗಣಿಸುತ್ತೇವೆ, ಹೀಗಾಗಿ ಹೊರಗಿನ ಲೂಪ್‌ನಿಂದಾಗಿ ನಾವು ರೇಖೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಒ (ಎನ್) ಹೊಂದಿದ್ದೇವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ: ಮೊಬೈಲ್ ಸಂಖ್ಯಾ ಕೀಪ್ಯಾಡ್ ಸಮಸ್ಯೆಗೆ ಒ (ಎನ್)

ನಾವು n ನ 1 ಆಯಾಮದ ಡಿಪಿ ಶ್ರೇಣಿಯನ್ನು ಹೊಂದಿರುವುದರಿಂದ. ನಾವು O (n) ನ ರೇಖೀಯ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿದ್ದೇವೆ.