Блог

Учитывая массив из N элементов и целое число M. Теперь массив изменяется путем замены некоторых элементов массива на -1. Задача состоит в том, чтобы распечатать исходный массив.
Элементы в исходном массиве связаны следующим образом: для каждого индекса i a[i] = (a[i-1]+1)% M.
It гарантируется, что в массиве есть одно ненулевое значение.

Примеры:

Input: arr[] = {5, -1, -1, 1, 2, 3}, M = 7
Output: 5 6 0 1 2 3
M = 7, so value at index 2 should be (5+1) % 7 = 6
value at index 3 should be (6+1) % 7 = 0

Input: arr[] = {5, -1, 7, -1, 9, 0}, M = 10
Output: 5 6 7 8 9 0 

Подход: Сначала найдите индекс неотрицательного значения индекса i. Затем просто идите в двух направлениях, то есть От i-1 до 0 и от i+1 до n.

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

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;

void construct(int n, int m, int a[])
{
	int ind = 0;

	// Finding the index which is not -1
	for (int i = 0; i < n; i++)
	{
		if (a[i] != -1)
		{
			ind = i;
			break;
		}
	}
	
	// Calculating the values of
	// the indexes ind-1 to 0
	for (int i = ind - 1; i > -1; i--)
	{
		if (a[i] == -1)
			a[i] = (a[i + 1] - 1 + m) % m;
	}
	
	// Calculating the values of
	// the indexes ind + 1 to n
	for (int i = ind + 1; i < n; i++)
	{
		if (a[i] == -1)
			a[i] = (a[i - 1] + 1) % m;
	}
	for (int i = 0; i < n; i++)
	{
		cout<< a[i] << " ";
	}

}

// Driver code
int main()
{

	int n = 6, m = 7;
	int a[] = { 5, -1, -1, 1, 2, 3 };
	construct(n, m, a);
	return 0;
}

// This code is contributed by 29AjayKumar

// Java implementation of the above approach
class GFG
{
	static void construct(int n, int m, int[] a)
	{
		int ind = 0;

		// Finding the index which is not -1
		for (int i = 0; i < n; i++)
		{
			if (a[i] != -1)
			{
				ind = i;
				break;
			}
		}
		
		// Calculating the values of
		// the indexes ind-1 to 0
		for (int i = ind - 1; i > -1; i--)
		{
			if (a[i] == -1)
				a[i] = (a[i + 1] - 1 + m) % m;
		}
		
		// Calculating the values of
		// the indexes ind + 1 to n
		for (int i = ind + 1; i < n; i++)
		{
			if (a[i] == -1)
				a[i] = (a[i - 1] + 1) % m;
		}
		for (int i = 0; i < n; i++)
		{
			System.out.print(a[i] + " ");
		}

	}

	// Driver code
	public static void main(String[] args)
	{
		int n = 6, m = 7;
		int[] a = { 5, -1, -1, 1, 2, 3 };
		construct(n, m, a);
	}
}

// This code is contributed by 29AjayKumar

# Python implementation of the above approach
def construct(n, m, a):
	ind = 0

	# Finding the index which is not -1
	for i in range(n):
		if (a[i]!=-1):
			ind = i
			break

	# Calculating the values of the indexes ind-1 to 0
	for i in range(ind-1, -1, -1):
		if (a[i]==-1):
			a[i]=(a[i + 1]-1 + m)% m

	# Calculating the values of the indexes ind + 1 to n
	for i in range(ind + 1, n):
		if(a[i]==-1):
			a[i]=(a[i-1]+1)% m
	print(*a)

# Driver code
n, m = 6, 7
a =[5, -1, -1, 1, 2, 3]
construct(n, m, a)

// C# implementation of the above approach
using System;

class GFG
{
	static void construct(int n, int m, int[] a)
	{
		int ind = 0;

		// Finding the index which is not -1
		for (int i = 0; i < n; i++)
		{
			if (a[i] != -1)
			{
				ind = i;
				break;
			}
		}
		
		// Calculating the values of
		// the indexes ind-1 to 0
		for (int i = ind - 1; i > -1; i--)
		{
			if (a[i] == -1)
				a[i] = (a[i + 1] - 1 + m) % m;
		}
		
		// Calculating the values of
		// the indexes ind + 1 to n
		for (int i = ind + 1; i < n; i++)
		{
			if (a[i] == -1)
				a[i] = (a[i - 1] + 1) % m;
		}
		for (int i = 0; i < n; i++)
		{
			Console.Write(a[i] + " ");
		}

	}

	// Driver code
	public static void Main(String[] args)
	{
		int n = 6, m = 7;
		int[] a = { 5, -1, -1, 1, 2, 3 };
		construct(n, m, a);
	}
}

// This code is contributed by 29AjayKumar

<script>

// Javascript implementation of above approach

function construct(n, m, a)
{
	var ind = 0;

	// Finding the index which is not -1
	for (var i = 0; i < n; i++)
	{
		if (a[i] != -1)
		{
			ind = i;
			break;
		}
	}
	
	// Calculating the values of
	// the indexes ind-1 to 0
	for (var i = ind - 1; i > -1; i--)
	{
		if (a[i] == -1)
			a[i] = (a[i + 1] - 1 + m) % m;
	}
	
	// Calculating the values of
	// the indexes ind + 1 to n
	for (var i = ind + 1; i < n; i++)
	{
		if (a[i] == -1)
			a[i] = (a[i - 1] + 1) % m;
	}
	for (var i = 0; i < n; i++)
	{
		document.write( a[i] + " ");
	}

}

// Driver code
var n = 6, m = 7;
var a = [5, -1, -1, 1, 2, 3];
construct(n, m, a);

</script>

Выход:

5 6 0 1 2 3