Минимизируйте операции, необходимые для того, чтобы каждый элемент массива равнялся его значению индекса

Опубликовано: 1 Января, 2022

Для массива arr [], состоящего из N целых чисел, задача состоит в том, чтобы изменить массив таким образом, чтобы arr [index] = index, используя минимальное количество операций следующего типа:

Выберите любой индекс i и любое целое число X и добавьте X ко всем элементам в диапазоне [0, i] .
Выберите любой индекс i и любое целое число X и замените arr [j] на arr [j]% X, где 0 ≤ j ≤ i .

Для каждой выполненной операции выведите следующее:

Для 1-й операции: напечатайте 1 i X
Для 2-й операции: напечатайте 2 i X

Примечание. Можно применить максимум N + 1 операций.

Примеры:

Input: arr[] = {7, 6, 3}, N = 3
Output:
1 2 5
1 1 2
1 0 1
2 2 3
Explanation:
1st operation: Adding 5 to all the elements till index 2 modifies array to {12, 11, 8}.
2nd operation: Adding 2 to all the elements till index 1 modifies array to {14, 13, 8}.
3rd operation: Adding 1 to all the elements till index 0 modifies array to {15, 13, 8}.
4th operation: Adding 3 to all the elements till index 2 modifies array to {0, 1, 2}.
So after 4 operations, the required array is obtained.
Input: arr[] = {3, 4, 5, 6}, N = 4
Output:
1 3 5
1 2 4
1 1 4
1 0 4
2 3 4

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: эту проблему можно решить с помощью жадного подхода. Ниже приведены шаги:

Примените N операций типа 1, где i- ^я операция заключается в добавлении X = (N + i - (arr [i]% N)) до индекса i путем обхода массива в обратном порядке. Для каждой i- ^й операции выведите «1 i X» .
После выполнения вышеуказанных N операций массив будет иметь вид arr [i]% N = i для 0 ≤ i <N .
Необходимо выполнить еще одну операцию, которая заключается в выполнении по модулю каждого элемента массива с N, то есть операцию «2 (N-1) N» .
После выполнения вышеуказанных операций для каждого индекса i arr [i] = i .

Ниже представлена реализация описанного выше подхода:

C ++

 // CPP program for the above approach
 #include <bits/stdc++.h>
 using namespace std;
 // Function which makes the given
 // array increasing using given
 // operations
 void makeIncreasing( int arr[], int N)
 {
    // The ith operation will be
    // 1 i N + i - arr[i] % N
    for ( int x = N - 1; x >= 0; x--)
    {
        int val = arr[x]; 
        // Find the value to be added
        // in each operation
        int add = N - val % N + x; 
        // Print the operation
        cout << "1 " << x << " " << add << endl; 
        // Performing the operation
        for ( int y = x; y >= 0; y--) {
            arr[y] += add;
        }
    }
    // Last modulo with N operation
    int mod = N;
    cout << "2 " << N - 1 << " " << mod << endl;
    for ( int x = N - 1; x >= 0; x--) {
        arr[x] %= mod;
    }
 }
 // Driver Code
 int main()
 {
    // Given array arr[]
    int arr[] = { 7, 6, 3 };
    int N = sizeof (arr) / sizeof (arr[0]); 
    // Function Call
    makeIncreasing(arr, N);
 }

Джава

 // Java Program for the above approach
 import java.util.*;
 class GFG
 {
    // Function which makes the given
    // array increasing using given
    // operations
    static void makeIncreasing( int arr[], int N)
    {
        // The ith operation will be
        // 1 i N + i - arr[i] % N
        for ( int x = N - 1 ; x >= 0 ; x--)
        {
            int val = arr[x]; 
            // Find the value to be added
            // in each operation
            int add = N - val % N + x; 
            // Print the operation
            System.out.println( "1"
                               + " " + x + " " + add); 
            // Performing the operation
            for ( int y = x; y >= 0 ; y--)
            {
                arr[y] += add;
            }
        }
        // Last modulo with N operation
        int mod = N; 
        System.out.println( "2"
                           + " " + (N - 1 ) + " " + mod); 
        for ( int x = N - 1 ; x >= 0 ; x--)
        {
            arr[x] %= mod;
        }
    }
    // Driver code
    public static void main(String[] args)
    {
        // Given array arr[]
        int arr[] = { 7 , 6 , 3 };
        int N = arr.length;
        // Function Call
        makeIncreasing(arr, N);
    }
 }

Python3

 # python Program for the above problem
 # Function which makes the given
 # array increasing using given
 # operations
 def makeIncreasing(arr, N):
    
    # The ith operation will be
    # 1 i N + i - arr[i] % N
    for x in range ( N - 1 , - 1 , - 1 ):
        val = arr[x]
        
        # Find the value to be added
        # in each operation
        add = N - val % N + x
        
        # Print the operation
        print ( "1" + " " + str (x) + " " + str (add))
        
        # Performing the operation
        for y in range (x, - 1 , - 1 ):
            arr[y] + = add
    
    # Last modulo with N operation
    mod = N;
    print ( "2" + " " + str (N - 1 ) + " " + str (mod))
    for i in range ( N - 1 , - 1 , - 1 ):
        arr[i] = arr[i] % mod
 # Driver code
 # Given array arr
 arr = [ 7 , 6 , 3 ]
 N = len (arr)
 # Function Call
 makeIncreasing(arr, N)

C #

 // C# Program for the above approach
 using System;
 class GFG
 {
    // Function which makes the given
    // array increasing using given
    // operations
    static void makeIncreasing( int [] arr, int N)
    {
        // The ith operation will be
        // 1 i N + i - arr[i] % N
        for ( int x = N - 1; x >= 0; x--)
        {
            int val = arr[x]; 
            // Find the value to be added
            // in each operation
            int add = N - val % N + x; 
            // Print the operation
            Console.WriteLine( "1"
                              + " " + x + " " + add); 
            // Performing the operation
            for ( int y = x; y >= 0; y--)
            {
                arr[y] += add;
            }
        }
        // Last modulo with N operation
        int mod = N; 
        Console.WriteLine( "2"
                          + " " + (N - 1) + " " + mod); 
        for ( int x = N - 1; x >= 0; x--) {
            arr[x] %= mod;
        }
    }
    // Driver code
    public static void Main()
    {
        // Given array arr[]
        int [] arr = new int [] { 7, 6, 3 }; 
        int N = arr.Length; 
        // Function Call
        makeIncreasing(arr, N);
    }
 }

Javascript

 <script>
      // JavaScript Program for the above approach
      
      // Function which makes the given
      // array increasing using given
      // operations
      function makeIncreasing(arr, N)
      {
        // The ith operation will be
        // 1 i N + i - arr[i] % N
        for ( var x = N - 1; x >= 0; x--) {
          var val = arr[x]; 
          // Find the value to be added
          // in each operation
          var add = N - (val % N) + x; 
          // Print the operation
          document.write( "1" + " " + x + " "
          + add + "<br>" ); 
          // Performing the operation
          for ( var y = x; y >= 0; y--) {
            arr[y] += add;
          }
        }
        // Last modulo with N operation
        var mod = N; 
        document.write( "2" + " " + (N - 1) + " "
        + mod + "<br>" ); 
        for ( var x = N - 1; x >= 0; x--) {
          arr[x] %= mod;
        }
      }
      // Driver code
      
      // Given array arr[]
      var arr = [7, 6, 3];
      var N = arr.length; 
      // Function Call
      makeIncreasing(arr, N);
      
</script>

Выход

Сложность времени: O (N ² )
Вспомогательное пространство: O (1)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Олимпиады по программированию Алгоритмы Структуры данных

Минимизируйте операции, необходимые для того, чтобы каждый элемент массива равнялся его значению индекса

C ++

Джава

Python3

C #

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ