n개의 숫자로 구성된 집합 S가 주어지면 각 하위 집합의 마지막 요소와 첫 번째 요소 간의 차이의 합을 찾습니다. 입력 집합 S에 나타나는 것과 동일한 순서로 유지하여 모든 하위 집합의 첫 번째 요소와 마지막 요소를 찾습니다. 즉, sumSetDiff(S) = ? (last(s) - first(s)) 여기서 합계는 S의 모든 하위 집합 s에 적용됩니다.

메모:

자바에서 const는 무엇입니까?

하위 집합의 요소는 집합 S와 동일한 순서로 되어 있어야 합니다. 예:

S = {5 2 9 6} n = 4  
Subsets are:  
{5} last(s)-first(s) = 0.  
{2} last(s)-first(s) = 0.  
{9} last(s)-first(s) = 0.  
{6} last(s)-first(s) = 0.  
{52} last(s)-first(s) = -3.  
{59} last(s)-first(s) = 4.  
{56} last(s)-first(s) = 1.  
{29} last(s)-first(s) = 7.  
{26} last(s)-first(s) = 4.  
{96} last(s)-first(s) = -3.  
{529} last(s)-first(s) = 4.  
{526} last(s)-first(s) = 1.  
{596} last(s)-first(s) = 1.  
{296} last(s)-first(s) = 4.  
{5296} last(s)-first(s) = 1.  
Output = -3+4+1+7+4-3+4+1+1+4+1  
 = 21.  

추천 : '에서 해결해주세요 관행 ' 먼저 솔루션으로 넘어가기 전에.

간단한 솔루션

Java에 있는 동안 수행

이 문제의 경우 집합 S의 각 하위 집합 s에 대한 마지막 요소와 첫 번째 요소 간의 차이를 찾고 이러한 차이의 합을 출력하는 것입니다. 이 접근 방식의 시간 복잡도는 O(2

^N

).

최대 절전 모드 방언

효율적인 솔루션

선형 시간복잡도 문제를 해결하기 위해 n개의 숫자로 구성된 집합 S가 주어지고 S의 각 하위 집합의 마지막 요소와 첫 번째 요소 간의 차이의 합을 계산해야 합니다. 즉, sumSetDiff(S) = ? (last(s) - first(s)) 여기서 합계는 S의 모든 하위 집합 s에 적용됩니다. 동등하게 sumSetDiff(S) = ? (마지막) - ? (first(s)) 즉, 각 하위 집합의 마지막 요소의 합과 각 하위 집합의 첫 번째 요소의 합을 개별적으로 계산한 다음 그 차이를 계산할 수 있습니다. S의 요소가 {a1 a2 a3...an}이라고 가정해 보겠습니다. 다음 관찰에 유의하십시오.

1. 요소를 포함하는 하위 집합 a1 첫 번째 요소는 {a2 a3...an}의 하위 집합을 가져온 다음 여기에 a1을 포함하여 얻을 수 있습니다. 해당 하위 집합의 수는 2입니다.^n-1.
2. a2 요소를 첫 번째 요소로 포함하는 하위 집합은 {a3 a4...an}의 하위 집합을 취한 다음 여기에 a2를 포함하여 얻을 수 있습니다. 해당 하위 집합의 수는 2입니다.^n-2.
3. 첫 번째 요소로 ai 요소를 포함하는 하위 집합은 {ai a(i+1)...an}의 하위 집합을 취한 다음 여기에 ai를 포함하여 얻을 수 있습니다. 해당 하위 집합의 수는 2입니다.^아니.
4. 
   
5. 따라서 모든 하위 집합의 첫 번째 요소의 합은 다음과 같습니다. SumF = a1.2
6. ^n-1
7. + a2.2
8. ^n-2
9. +...+ an.1 비슷한 방법으로 S의 모든 하위 집합 중 마지막 요소의 합을 계산할 수 있습니다(모든 단계에서 ai를 첫 번째 요소 대신 마지막 요소로 취한 다음 모든 하위 집합을 얻음). 합계 = a1.1 + a2.2 +...+ an.2
10. ^n-1
11. 마지막으로 우리 문제의 답은 다음과 같습니다.
12. 합계 - 합계F
13. .
14. 구현:
15. C++

    // A C++ program to find sum of difference between // last and first element of each subset #include   // Returns the sum of first elements of all subsets int SumF(int S[] int n) {  int sum = 0;  // Compute the SumF as given in the above explanation  for (int i = 0; i < n; i++)  sum = sum + (S[i] * pow(2 n-i-1));  return sum; } // Returns the sum of last elements of all subsets int SumL(int S[] int n) {  int sum = 0;  // Compute the SumL as given in the above explanation  for (int i = 0; i < n; i++)  sum = sum + (S[i] * pow(2 i));  return sum; } // Returns the difference between sum of last elements of // each subset and the sum of first elements of each subset int sumSetDiff(int S[] int n) {  return SumL(S n) - SumF(S n); } // Driver program to test above function int main() {  int n = 4;  int S[] = {5 2 9 6};  printf('%dn' sumSetDiff(S n));  return 0; } 

    Java

    // A Java program to find sum of difference  // between last and first element of each  // subset class GFG {    // Returns the sum of first elements   // of all subsets  static int SumF(int S[] int n)  {  int sum = 0;  // Compute the SumF as given in   // the above explanation  for (int i = 0; i < n; i++)  sum = sum + (int)(S[i] *   Math.pow(2 n - i - 1));  return sum;  }  // Returns the sum of last elements   // of all subsets  static int SumL(int S[] int n)  {  int sum = 0;  // Compute the SumL as given in   // the above explanation  for (int i = 0; i < n; i++)  sum = sum + (int)(S[i] *  Math.pow(2 i));    return sum;  }  // Returns the difference between sum   // of last elements of each subset and   // the sum of first elements of each   // subset  static int sumSetDiff(int S[] int n)  {  return SumL(S n) - SumF(S n);  }  // Driver program  public static void main(String arg[])  {  int n = 4;  int S[] = { 5 2 9 6 };    System.out.println(sumSetDiff(S n));  } } // This code is contributed by Anant Agarwal. 

    Python3

    # Python3 program to find sum of # difference between last and  # first element of each subset # Returns the sum of first # elements of all subsets def SumF(S n): sum = 0 # Compute the SumF as given # in the above explanation for i in range(n): sum = sum + (S[i] * pow(2 n - i - 1)) return sum # Returns the sum of last # elements of all subsets def SumL(S n): sum = 0 # Compute the SumL as given # in the above explanation for i in range(n): sum = sum + (S[i] * pow(2 i)) return sum # Returns the difference between sum # of last elements of each subset and # the sum of first elements of each subset def sumSetDiff(S n): return SumL(S n) - SumF(S n) # Driver program n = 4 S = [5 2 9 6] print(sumSetDiff(S n)) # This code is contributed by Anant Agarwal. 

    C#

     // A C# program to find sum of difference  // between last and first element of each  // subset using System; class GFG {    // Returns the sum of first elements   // of all subsets  static int SumF(int []S int n)  {  int sum = 0;    // Compute the SumF as given in   // the above explanation  for (int i = 0; i < n; i++)  sum = sum + (int)(S[i] *   Math.Pow(2 n - i - 1));  return sum;  }    // Returns the sum of last elements   // of all subsets  static int SumL(int []S int n)  {  int sum = 0;    // Compute the SumL as given in   // the above explanation  for (int i = 0; i < n; i++)  sum = sum + (int)(S[i] *  Math.Pow(2 i));    return sum;  }    // Returns the difference between sum   // of last elements of each subset and   // the sum of first elements of each   // subset  static int sumSetDiff(int []S int n)  {  return SumL(S n) - SumF(S n);  }    // Driver program  public static void Main()  {  int n = 4;  int []S = { 5 2 9 6 };    Console.Write(sumSetDiff(S n));  } }   // This code is contributed by nitin mittal. 

    JavaScript

    // Returns the sum of first elements of all subsets function sumF(S n) {  let sum = 0;  // Compute the SumF as given in the above explanation  for (let i = 0; i < n; i++) {  sum += S[i] * Math.pow(2 n - i - 1);  }  return sum; } // Returns the sum of last elements of all subsets function sumL(S n) {  let sum = 0;  // Compute the SumL as given in the above explanation  for (let i = 0; i < n; i++) {  sum += S[i] * Math.pow(2 i);  }  return sum; } // Returns the difference between sum of last elements of each subset and the sum of first elements of each subset function sumSetDiff(S n) {  return sumL(S n) - sumF(S n); } // Driver program to test the above functions function main() {  const n = 4;  const S = [5 2 9 6];  console.log(sumSetDiff(S n)); } main(); 

    PHP

     // A PHP program to find sum  // of difference between last  // and first element of each subset // Returns the sum of first  // elements of all subsets function SumF( $S $n) { $sum = 0; // Compute the SumF as given  // in the above explanation for ($i = 0; $i < $n; $i++) $sum = $sum + ($S[$i] * pow(2 $n - $i - 1)); return $sum; } // Returns the sum of last // elements of all subsets function SumL( $S $n) { $sum = 0; // Compute the SumL as given // in the above explanation for($i = 0; $i < $n; $i++) $sum = $sum + ($S[$i] * pow(2 $i)); return $sum; } // Returns the difference between // sum of last elements of // each subset and the sum of // first elements of each subset function sumSetDiff( $S $n) { return SumL($S $n) - SumF($S $n); } // Driver Code $n = 4; $S = array(5 2 9 6); echo sumSetDiff($S $n); // This code is contributed by anuj_67. ?> 

16. 산출:

17. 21  
    

18. 시간 복잡도 : O(n) 이 기사는 기고자:
19. 아카쉬 아가르왈
20. . GeeksforGeeks를 좋아하고 기여하고 싶다면 다음을 사용하여 기사를 작성할 수도 있습니다.
21. Contribute.geeksforgeeks.org
22. 또는 귀하의 기사를 [email protected]로 우편으로 보내주십시오. GeeksforGeeks 메인 페이지에 나타나는 기사를 보고 다른 Geeks를 도와주세요.