عد التباديل التي تنتج نتيجة إيجابية

بالنظر إلى مجموعة من الأرقام بطول n > 1 رقم تقع ضمن النطاق من 0 إلى 9. نقوم بإجراء تسلسل من العمليات الثلاث أدناه حتى ننتهي من جميع الأرقام
 

  1. حدد بداية من رقمين ثم أضف ( + )
  2. ثم يتم طرح الرقم التالي (-) من نتيجة الخطوة أعلاه. 
     
  3. يتم ضرب نتيجة الخطوة أعلاه (X) بالرقم التالي.


نقوم بتنفيذ تسلسل العمليات أعلاه خطيًا مع الأرقام المتبقية. 
وتتمثل المهمة في العثور على عدد التباديل للصفيف المحدد الذي ينتج نتيجة إيجابية بعد العمليات المذكورة أعلاه.
على سبيل المثال، ضع في اعتبارك رقم الإدخال[] = {1 2 3 4 5}. دعونا نفكر في التقليب 21345 لتوضيح تسلسل العمليات. 

  1. أضف أول رقمين = 2+1 = 3
  2. اطرح نتيجة الرقم التالي = النتيجة 3 = 3-3 = 0
  3. ضرب نتيجة الرقم التالي = النتيجة * 4 = 0 * 4 = 0
  4. أضف نتيجة الرقم التالي = النتيجة+5 = 0+5 = 5
  5. النتيجة = 5 وهي إيجابية لذا قم بزيادة العدد بمقدار واحد


أمثلة: 
 

Input : number[]='123' Output: 4 // here we have all permutations // 123 --> 1+2 -> 3-3 -> 0 // 132 --> 1+3 -> 4-2 -> 2 ( positive ) // 213 --> 2+1 -> 3-3 -> 0 // 231 --> 2+3 -> 5-1 -> 4 ( positive ) // 312 --> 3+1 -> 4-2 -> 2 ( positive ) // 321 --> 3+2 -> 5-1 -> 4 ( positive ) // total 4 permutations are giving positive result Input : number[]='112' Output: 2 // here we have all permutations possible // 112 --> 1+1 -> 2-2 -> 0 // 121 --> 1+2 -> 3-1 -> 2 ( positive ) // 211 --> 2+1 -> 3-1 -> 2 ( positive ) 


سئل في : مورجان ستانلي
 


نقوم أولاً بإنشاء جميع التباديل الممكنة لمجموعة أرقام معينة وتنفيذ تسلسل معين من العمليات بشكل تسلسلي على كل تبديل والتحقق من أن نتيجة التقليب إيجابية. يصف الكود أدناه حل المشكلة بسهولة.
ملحوظة : يمكننا إنشاء جميع التباديل الممكنة إما باستخدام الطريقة التكرارية انظر هذا المادة أو يمكننا استخدام وظيفة STL next_permutation() وظيفة لتوليدها. 
 

C++
   // C++ program to find count of permutations that produce   // positive result.   #include       using     namespace     std  ;   // function to find all permutation after executing given   // sequence of operations and whose result value is positive   // result > 0 ) number[] is array of digits of length of n   int     countPositivePermutations  (  int     number  []     int     n  )   {      // First sort the array so that we get all permutations      // one by one using next_permutation.      sort  (  number       number  +  n  );      // Initialize result (count of permutations with positive      // result)      int     count     =     0  ;      // Iterate for all permutation possible and do operation      // sequentially in each permutation      do      {      // Stores result for current permutation. First we      // have to select first two digits and add them      int     curr_result     =     number  [  0  ]     +     number  [  1  ];      // flag that tells what operation we are going to      // perform      // operation = 0 ---> addition operation ( + )      // operation = 1 ---> subtraction operation ( - )      // operation = 0 ---> multiplication operation ( X )      // first sort the array of digits to generate all      // permutation in sorted manner      int     operation     =     1  ;      // traverse all digits      for     (  int     i  =  2  ;     i   <  n  ;     i  ++  )      {      // sequentially perform +  -  X operation      switch     (  operation  )      {      case     0  :      curr_result     +=     number  [  i  ];      break  ;      case     1  :      curr_result     -=     number  [  i  ];      break  ;      case     2  :      curr_result     *=     number  [  i  ];      break  ;      }      // next operation (decides case of switch)      operation     =     (  operation     +     1  )     %     3  ;      }      // result is positive then increment count by one      if     (  curr_result     >     0  )      count  ++  ;      // generate next greater permutation until it is      // possible      }     while  (  next_permutation  (  number       number  +  n  ));      return     count  ;   }   // Driver program to test the case   int     main  ()   {      int     number  []     =     {  1       2       3  };      int     n     =     sizeof  (  number  )  /  sizeof  (  number  [  0  ]);      cout      < <     countPositivePermutations  (  number       n  );      return     0  ;   }   
Java
   // Java program to find count of permutations    // that produce positive result.    import     java.util.*  ;   class   GFG      {   // function to find all permutation after    // executing given sequence of operations    // and whose result value is positive result > 0 )    // number[] is array of digits of length of n    static     int     countPositivePermutations  (  int     number  []           int     n  )      {         // First sort the array so that we get       // all permutations one by one using      // next_permutation.       Arrays  .  sort  (  number  );         // Initialize result (count of permutations       // with positive result)       int     count     =     0  ;         // Iterate for all permutation possible and       // do operation sequentially in each permutation       do      {         // Stores result for current permutation.       // First we have to select first two digits      // and add them       int     curr_result     =     number  [  0  ]     +     number  [  1  ]  ;         // flag that tells what operation we are going to       // perform       // operation = 0 ---> addition operation ( + )       // operation = 1 ---> subtraction operation ( - )       // operation = 0 ---> multiplication operation ( X )       // first sort the array of digits to generate all       // permutation in sorted manner       int     operation     =     1  ;         // traverse all digits       for     (  int     i     =     2  ;     i      <     n  ;     i  ++  )         {         // sequentially perform +  -  X operation       switch     (  operation  )         {         case     0  :         curr_result     +=     number  [  i  ]  ;         break  ;         case     1  :         curr_result     -=     number  [  i  ]  ;         break  ;         case     2  :         curr_result     *=     number  [  i  ]  ;         break  ;         }         // next operation (decides case of switch)       operation     =     (  operation     +     1  )     %     3  ;         }         // result is positive then increment count by one       if     (  curr_result     >     0  )         count  ++  ;         // generate next greater permutation until       // it is possible       }     while  (  next_permutation  (  number  ));         return     count  ;      }      static     boolean     next_permutation  (  int  []     p  )   {      for     (  int     a     =     p  .  length     -     2  ;     a     >=     0  ;     --  a  )      if     (  p  [  a  ]      <     p  [  a     +     1  ]  )      for     (  int     b     =     p  .  length     -     1  ;;     --  b  )      if     (  p  [  b  ]     >     p  [  a  ]  )         {      int     t     =     p  [  a  ]  ;      p  [  a  ]     =     p  [  b  ]  ;      p  [  b  ]     =     t  ;      for     (  ++  a       b     =     p  .  length     -     1  ;     a      <     b  ;     ++  a       --  b  )         {      t     =     p  [  a  ]  ;      p  [  a  ]     =     p  [  b  ]  ;      p  [  b  ]     =     t  ;      }      return     true  ;      }      return     false  ;   }   // Driver Code   public     static     void     main  (  String  []     args  )   {      int     number  []     =     {  1       2       3  };         int     n     =     number  .  length  ;         System  .  out  .  println  (  countPositivePermutations  (  number       n  ));      }   }      // This code is contributed by PrinciRaj1992   
Python3
   # Python3 program to find count of permutations    # that produce positive result.    # function to find all permutation after    # executing given sequence of operations    # and whose result value is positive result > 0 )    # number[] is array of digits of length of n    def   countPositivePermutations  (  number     n  ):   # First sort the array so that we get    # all permutations one by one using   # next_permutation.    number  .  sort  ()   # Initialize result (count of permutations    # with positive result)    count   =   0  ;   # Iterate for all permutation possible and    # do operation sequentially in each permutation    while   True  :   # Stores result for current permutation.    # First we have to select first two digits   # and add them    curr_result   =   number  [  0  ]   +   number  [  1  ];   # flag that tells what operation we are going to    # perform    # operation = 0 ---> addition operation ( + )    # operation = 1 ---> subtraction operation ( - )    # operation = 0 ---> multiplication operation ( X )    # first sort the array of digits to generate all    # permutation in sorted manner    operation   =   1  ;   # traverse all digits    for   i   in   range  (  2     n  ):   # sequentially perform +  -  X operation    if   operation   ==   0  :   curr_result   +=   number  [  i  ];   else   if   operation   ==   1  :   curr_result   -=   number  [  i  ];   else   if   operation   ==   2  :   curr_result   *=   number  [  i  ];   # next operation (decides case of switch)    operation   =   (  operation   +   1  )   %   3  ;   # result is positive then increment count by one    if   (  curr_result   >   0  ):   count   +=   1   # generate next greater permutation until    # it is possible    if  (  not   next_permutation  (  number  )):   break   return   count  ;   def   next_permutation  (  p  ):   for   a   in   range  (  len  (  p  )  -  2     -  1     -  1  ):   if   (  p  [  a  ]    <   p  [  a   +   1  ]):   for   b   in   range  (  len  (  p  )  -  1     -  1000000000     -  1  ):   if   (  p  [  b  ]   >   p  [  a  ]):   t   =   p  [  a  ];   p  [  a  ]   =   p  [  b  ];   p  [  b  ]   =   t  ;   a   +=   1   b   =   len  (  p  )   -   1   while  (  a    <   b  ):   t   =   p  [  a  ];   p  [  a  ]   =   p  [  b  ];   p  [  b  ]   =   t  ;   a   +=   1   b   -=   1   return   True  ;   return   False  ;   # Driver Code   if   __name__   ==  '__main__'  :   number   =   [  1     2     3  ]   n   =   len  (  number  )   print  (  countPositivePermutations  (  number     n  ));   # This code is contributed by rutvik_56.   
C#
   // C# program to find count of permutations    // that produce positive result.    using     System  ;   class     GFG   {       // function to find all permutation after    // executing given sequence of operations    // and whose result value is positive result > 0 )    // number[] is array of digits of length of n    static     int     countPositivePermutations  (  int     []  number           int     n  )      {         // First sort the array so that we get       // all permutations one by one using      // next_permutation.       Array  .  Sort  (  number  );         // Initialize result (count of permutations       // with positive result)       int     count     =     0  ;         // Iterate for all permutation possible and       // do operation sequentially in each permutation       do      {         // Stores result for current permutation.       // First we have to select first two digits      // and add them       int     curr_result     =     number  [  0  ]     +     number  [  1  ];         // flag that tells what operation we are going to       // perform       // operation = 0 ---> addition operation ( + )       // operation = 1 ---> subtraction operation ( - )       // operation = 0 ---> multiplication operation ( X )       // first sort the array of digits to generate all       // permutation in sorted manner       int     operation     =     1  ;         // traverse all digits       for     (  int     i     =     2  ;     i      <     n  ;     i  ++  )         {         // sequentially perform +  -  X operation       switch     (  operation  )         {         case     0  :         curr_result     +=     number  [  i  ];         break  ;         case     1  :         curr_result     -=     number  [  i  ];         break  ;         case     2  :         curr_result     *=     number  [  i  ];         break  ;         }         // next operation (decides case of switch)       operation     =     (  operation     +     1  )     %     3  ;         }         // result is positive then increment count by one       if     (  curr_result     >     0  )         count  ++  ;         // generate next greater permutation until       // it is possible       }     while  (  next_permutation  (  number  ));         return     count  ;      }      static     bool     next_permutation  (  int  []     p  )   {      for     (  int     a     =     p  .  Length     -     2  ;     a     >=     0  ;     --  a  )      if     (  p  [  a  ]      <     p  [  a     +     1  ])      for     (  int     b     =     p  .  Length     -     1  ;;     --  b  )      if     (  p  [  b  ]     >     p  [  a  ])         {      int     t     =     p  [  a  ];      p  [  a  ]     =     p  [  b  ];      p  [  b  ]     =     t  ;      for     (  ++  a       b     =     p  .  Length     -     1  ;         a      <     b  ;     ++  a       --  b  )         {      t     =     p  [  a  ];      p  [  a  ]     =     p  [  b  ];      p  [  b  ]     =     t  ;      }      return     true  ;      }      return     false  ;   }   // Driver Code   static     public     void     Main     ()   {      int     []  number     =     {  1       2       3  };         int     n     =     number  .  Length  ;         Console  .  Write  (  countPositivePermutations  (  number       n  ));      }   }      // This code is contributed by ajit..   
JavaScript
    <  script  >      // Javascript program to find count of permutations      // that produce positive result.          // function to find all permutation after      // executing given sequence of operations      // and whose result value is positive result > 0 )      // number[] is array of digits of length of n      function     countPositivePermutations  (  number       n  )      {      // First sort the array so that we get      // all permutations one by one using      // next_permutation.      number  .  sort  (  function  (  a       b  ){  return     a     -     b  });      // Initialize result (count of permutations      // with positive result)      let     count     =     0  ;      // Iterate for all permutation possible and      // do operation sequentially in each permutation      do      {      // Stores result for current permutation.      // First we have to select first two digits      // and add them      let     curr_result     =     number  [  0  ]     +     number  [  1  ];      // flag that tells what operation we are going to      // perform      // operation = 0 ---> addition operation ( + )      // operation = 1 ---> subtraction operation ( - )      // operation = 0 ---> multiplication operation ( X )      // first sort the array of digits to generate all      // permutation in sorted manner      let     operation     =     1  ;      // traverse all digits      for     (  let     i     =     2  ;     i      <     n  ;     i  ++  )      {      // sequentially perform +  -  X operation      switch     (  operation  )      {      case     0  :      curr_result     +=     number  [  i  ];      break  ;      case     1  :      curr_result     -=     number  [  i  ];      break  ;      case     2  :      curr_result     *=     number  [  i  ];      break  ;      }      // next operation (decides case of switch)      operation     =     (  operation     +     1  )     %     3  ;      }      // result is positive then increment count by one      if     (  curr_result     >     0  )      count  ++  ;      // generate next greater permutation until      // it is possible      }     while  (  next_permutation  (  number  ));      return     count  ;      }      function     next_permutation  (  p  )      {      for     (  let     a     =     p  .  length     -     2  ;     a     >=     0  ;     --  a  )      if     (  p  [  a  ]      <     p  [  a     +     1  ])      for     (  let     b     =     p  .  length     -     1  ;;     --  b  )      if     (  p  [  b  ]     >     p  [  a  ])      {      let     t     =     p  [  a  ];      p  [  a  ]     =     p  [  b  ];      p  [  b  ]     =     t  ;      for     (  ++  a       b     =     p  .  length     -     1  ;      a      <     b  ;     ++  a       --  b  )      {      t     =     p  [  a  ];      p  [  a  ]     =     p  [  b  ];      p  [  b  ]     =     t  ;      }      return     true  ;      }      return     false  ;      }          let     number     =     [  1       2       3  ];      let     n     =     number  .  length  ;      document  .  write  (  countPositivePermutations  (  number       n  ));        <  /script>   

الإخراج:  

4 

تعقيد الوقت: O(n*n!)

المساحة المساعدة: O(1)
إذا كان لديك حل أفضل وأفضل لهذه المشكلة، فيرجى مشاركتها في التعليقات.