We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Construct the Array
  5. Discussions

Construct the Array

  • christopher_g_c2
     + 1 comment

    I have read the editorial. I find the explanation simple enough. However, I am still getting different answers from the tests. Test case 2: input: 761 99 1, result given by HackerRank: 236568308, result given by my code: 5776253194797940406 It is funny I should be getting different results because my code gives exactly same results when running against simple test cases using brute force. I also wrote a method which had time out issues. This also gives 5776253194797940406 for input 761 99 1. I also find it strange editorial talks about using Fermat's little Theorem when surely such optimization is done by the compiler?

    long long countArray(int n, int k, int x) 
{    
    long long retVal = 1;
	/*
	f(i) num ways to fill range [1, i] such that A1 = 1 and Ai != 1
	x != 1, answer is f(n)/(k - 1)
	x = 1, f(n - 1)


	f(i) = (k - 1)f(i - 2) + (k - 2)f(i - 1)
	*/

	long long f0 = 0;
	long long f1 = k - 1;

	int i = 2;

	while (++i < n)
	{
		if ((i % 2) != 0)
		{
			f0 = (k - 1) * f0 + (k - 2) * f1;
		}
		else
		{
			f1 = (k - 1) * f1 + (k - 2) * f0;
		}
	}

	if (x == 1)
	{
		if ((n % 2) != 0)
		{
			retVal = f1;
		}
		else
		{
			retVal = f0;
		}
	}
	else
	{
		if ((n % 2) != 0)
		{
			retVal = (k - 1) * f0 + (k - 2) * f1;
		}
		else
		{
			retVal = (k - 1) * f1 + (k - 2) * f0;
		}
		retVal /= (k - 1);
	}

	return retVal;
}

long long Power(long long x, long long y)
{
	long long retVal = x;

	for (int i = 1; i < y; i++)
	{
		retVal *= x;
	}
	return retVal;
}

long long countArrayInefficient(int n, int k, int x) 
{    
    long long retVal = 1;
	long long i = 1;
	retVal = Power(k - 1, n - 2);
	long long m = n - 2;

	while (--m > 0)
	{
		i = -i;
		retVal += i * Power(k-1, m);
	}

	if (x != 1)
	{
		if ((n % 2) == 0)
			retVal++;
		else
			retVal--;
	}
	return retVal;
}

long countArrayBruteForce(int n, int k, int x) 
{    
    long retval = 0;
    
	// crude method below:
	int *array = new int[n];

	array[0] = 1;
	array[n - 1] = x;

	int i = 1;

	for (int i = 1; i < n - 1; i++)
		array[i] = 1;

	bool end = false;

	int pos = n - 2;

	while (!end)
	{
		end = true;
		for (int i = 1; i < n - 1; i++)
		{
			if (array[i] != k)
			{
				end = false;
				break;
			}
		}

		if (array[pos] == k)
		{
			pos--;
		}
		else
		{
			array[pos]++;

			if (pos < n - 2)
			{
				pos++;
				array[pos] = 0;
			}
			else
			{
				bool valid = true;
				for (int i = 1; i < n; i++)
				{
					if (array[i] == array[i - 1])
					{
						valid = false;
						break;
					}
				}
				if (valid)
				{
					for (int i = 0; i < n; i++)
					{
						cout << array[i] << ' ';
					}
					cout << endl;

					retval++; 
				}
			}
			
		}
	
	}

	delete [] array;

    return retval; 
}