Изменить массив, сделав все элементы массива равными 0, вычитая K^i из элемента массива на каждом i-м шаге

Опубликовано: 22 Сентября, 2022

Для заданного массива arr[] размера N задача состоит в том, чтобы проверить, возможно ли преобразовать все элементы массива в 0 , вычитая K i из элемента массива на i -м шаге. Если это возможно, то выведите « Да ». В противном случае выведите « Нет ».

Примеры:

Input: N = 5, K = 2, arr[] = {8, 0, 3, 4, 80}
Output: Yes
Explanation: 
One possible sequence of operations is as follows:

  1. Subtract 20 from arr[2]( = 3 ). Thereafter, the array modifies to, arr[] = {8, 0, 2, 4, 32}.
  2. Subtract 21 from arr[2]( = 2 ). Thereafter, the array modifies to, arr[] = {8, 0, 0, 4, 32}.
  3. Subtract 22 from arr[3]( = 4 ). Thereafter, the array modifies to, arr[] = {8, 0, 0, 0, 32}.
  4. Subtract 23 from arr[1]( = 8 ). Thereafter, the array modifies to, arr[] = {0, 0, 0, 0, 32}.
  5. Do not subtract 24 from any array element.
  6. Subtract 25 from arr[4]( = 32 ). Thereafter, the array modifies to, arr[] = {0, 0, 0, 0, 0}.

Input: N = 3, K = 2, arr[] = {0, 1, 3}
Output: No

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

  • Инициализируйте вектор, скажем V, для хранения всех возможных степеней K.
  • Кроме того, инициализируйте map<int, int>, скажем, MP , чтобы сохранить, использовалась ли мощность K или нет.
  • Инициализируйте переменную, скажем, X как 1, чтобы сохранить количество степеней K.
  • Повторяйте до тех пор, пока X не меньше, чем INT_MAX, и выполните следующие шаги:
    • Вставьте значение X в вектор.
    • Умножьте Х на К.
  • Переберите диапазон [0, N – 1] , используя переменную i , и выполните следующие шаги:
    • Переберите вектор, V в обратном порядке, используя переменную j , и выполните следующие шаги:
      • Если arr[i] больше, чем V[j] и MP[V[j]] равно 0, то вычтите V[j] из arr[i] .
      • Обновите MP[V[j]] до 1 .
    • Если arr[i] не равно 0 , то выход из цикла.
  • Если i меньше N, то выведите «Нет», так как элементы массива нельзя сделать равными 0 . В противном случае выведите «Да» .

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

C++




// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether all array
// elements can be made zero or not
string isMakeZero(int arr[], int N, int K)
{
    // Stores if a power of K has
    // already been subtracted or not
    map<int, int> MP;
 
    // Stores all the Kth power
    vector<int> V;
 
    int X = 1;
    int i;
 
    // Iterate until X is
    // less than INT_MAX
    while (X > 0 && X < INT_MAX) {
        V.push_back(X);
        X *= K;
    }
 
    // Traverse the array arr[]
    for (i = 0; i < N; i++) {
 
        // Iterate over the range [0, M]
        for (int j = V.size() - 1; j >= 0; j--) {
 
            // If MP[V[j]] is 0 and V[j]
            // is less than or equal to arr[i]
            if (MP[V[j]] == 0 && V[j] <= arr[i]) {
                arr[i] -= V[j];
                MP[V[j]] = 1;
            }
        }
 
        // If arr[i] is not 0
        if (arr[i] != 0)
            break;
    }
 
    // If i is less than N
    if (i < N)
        return "No";
 
    // Otherwise,
    else
        return "Yes";
}
 
// Driver code
int main()
{
 
    int arr[] = { 8, 0, 3, 4, 80 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
 
    cout << isMakeZero(arr, N, K);
 
    return 0;
}

Java



// Java program for the above approach
import java.util.ArrayList;
import java.util.HashMap;
 
class GFG {
 
    // Function to check whether all array
    // elements can be made zero or not
    static String isMakeZero(int arr[], int N, int K)
    {
       
        // Stores if a power of K has
        // already been subtracted or not
        HashMap<Integer, Integer> MP = new HashMap<Integer, Integer>();
 
        // Stores all the Kth power
        ArrayList<Integer> V = new ArrayList<Integer>();
 
        int X = 1;
        int i;
 
        // Iterate until X is
        // less than INT_MAX
        while (X > 0 && X < Integer.MAX_VALUE) {
            V.add(X);
            X *= K;
        }
 
        // Traverse the array arr[]
        for (i = 0; i < N; i++) {
 
            // Iterate over the range [0, M]
            for (int j = V.size() - 1; j >= 0; j--) {
 
                // If MP[V[j]] is 0 and V[j]
                // is less than or equal to arr[i]
                if (MP.containsKey(V.get(j)) == false && V.get(j) <= arr[i]) {
                    arr[i] -= V.get(j);
                    MP.put(V.get(j), 1);
                }
            }
 
            // If arr[i] is not 0
            if (arr[i] != 0)
                break;
        }
 
        // If i is less than N
        if (i < N)
            return "No";
 
        // Otherwise,
        else
            return "Yes";
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        int arr[] = { 8, 0, 3, 4, 80 };
        int N = arr.length;
        int K = 2;
 
        System.out.println(isMakeZero(arr, N, K));
    }
}
 
// This code is contributed by _saurabh_jaiswal.
Python3



# Python Program for the above approach
 
# Function to check whether all array
# elements can be made zero or not
def isMakeZero(arr, N, K):
   
    # Stores if a power of K has
    # already been subtracted or not
    MP = {}
 
    # Stores all the Kth power
    V = []
 
    X = 1
 
    # Iterate until X is
    # less than INT_MAX
    while (X > 0 and X < 10**20):
        V.append(X)
        X *= K
 
    # Traverse the array arr[]
    for i in range(0, N, 1):
 
        # Iterate over the range [0, M]
        for j in range(len(V) - 1, -1, -1):
 
            # If MP[V[j]] is 0 and V[j]
            # is less than or equal to arr[i]
            if (V[j] not in MP and V[j] <= arr[i]):
                arr[i] -= V[j]
                MP[V[j]] = 1
 
        # If arr[i] is not 0
        if (arr[i] != 0):
            break
 
    # If i is less than N - 1
 
    if (i < N - 1):
        return "No"
 
    # Otherwise,
    else:
        return "Yes"
 
# Driver code
arr = [8, 0, 3, 4, 80]
N = len(arr)
K = 2
 
print(isMakeZero(arr, N, K))
 
# This code is contributed by _saurabh_jaiswal
C#



// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
   // Function to check whether all array
    // elements can be made zero or not
    static string isMakeZero(int[] arr, int N, int K)
    {
       
        // Stores if a power of K has
        // already been subtracted or not
        Dictionary<int,int> MP = new Dictionary<int,int>();
 
        // Stores all the Kth power
        List<int> V = new List<int>();
 
        int X = 1;
        int i;
 
        // Iterate until X is
        // less than INT_MAX
        while (X > 0 && X < Int32.MaxValue) {
            V.Add(X);
            X *= K;
        }
 
        // Traverse the array arr[]
        for (i = 0; i < N; i++) {
 
            // Iterate over the range [0, M]
            for (int j = V.Count - 1; j >= 0; j--) {
 
                // If MP[V[j]] is 0 and V[j]
                // is less than or equal to arr[i]
                if (MP.ContainsKey(V[j]) == false && V[j] <= arr[i]) {
                    arr[i] -= V[j];
                    MP[V[j]] = 1;
                }
            }
 
            // If arr[i] is not 0
            if (arr[i] != 0)
                break;
        }
 
        // If i is less than N
        if (i < N)
            return "No";
 
        // Otherwise,
        else
            return "Yes";
    }
 
// Driver Code
public static void Main(String[] args)
{
    int[] arr = { 8, 0, 3, 4, 80 };
        int N = arr.Length;
        int K = 2;
 
        Console.WriteLine(isMakeZero(arr, N, K));
}
}
 
// This code is contributed by splevel62.
Javascript



<script>
        // JavaScript Program for the above approach
 
 
        // Function to check whether all array
        // elements can be made zero or not
        function isMakeZero(arr, N, K) {
            // Stores if a power of K has
            // already been subtracted or not
            let MP = new Map();
 
            // Stores all the Kth power
            let V = [];
 
            let X = 1;
            let i;
 
            // Iterate until X is
            // less than INT_MAX
            while (X > 0 && X < Number.MAX_VALUE) {
                V.push(X);
                X *= K;
            }
 
            // Traverse the array arr[]
            for (i = 0; i < N; i++) {
 
                // Iterate over the range [0, M]
                for (let j = V.length - 1; j >= 0; j--) {
 
                    // If MP[V[j]] is 0 and V[j]
                    // is less than or equal to arr[i]
                    if (MP.has(V[j]) == false && V[j] <= arr[i]) {
                        arr[i] -= V[j];
                        MP.set(V[j], 1);
                    }
                }
 
                // If arr[i] is not 0
                if (arr[i] != 0)
                    break;
            }
 
            // If i is less than N
            if (i < N)
                return "No";
 
            // Otherwise,
            else
                return "Yes";
        }
 
        // Driver code
 
        let 
            

                            

                    
                                            Mathematical
                                    

                        

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

                

                                            

                            
Разделите два числа с помощью двоичного поиска без использования оператора / и %

                            
15 Февраля, 2023

                        

                                            

                            
Подсчитайте пары, разница между которыми и индексами различна.

                            
15 Февраля, 2023

                        

                                            

                            
Назначьте N задач N людям, чтобы минимизировать общее время

                            
14 Февраля, 2023

                        

                                            

                            
Разделить массив на максимальное количество подмассивов, чтобы сумма чередующихся сумм была равна 0

                            
14 Февраля, 2023

                        

                                            

                            
Максимальное побитовое ИЛИ для любых двух подстрок заданной двоичной строки

                            
14 Февраля, 2023

                        

                                            

                            
Максимизируйте сумму средних значений пар, сделанных с использованием элементов X [] и Y []

                            
14 Февраля, 2023

                        

                                            

                            
Найдите X, чтобы большинство элементов массива имели форму (X + p*K)

                            
14 Февраля, 2023

                        

                                            

                            
Создайте отсортированный массив таким образом, чтобы setbit в побитовом XOR любой пары был четным.

                            
21 Января, 2023