CHEFDMND - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest

Setter: nitjchapter
Tester: nitjchapter
Editorialist: nitjchapter

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Backtracking

PROBLEM:

Chef finds square numbers very interesting. While he was lost finding patterns among numbers, he named a category of them as Diamondnumbers, and wanted to explore them more.
According to Chef, a Diamondnumber is a number whose squares of the digits add up to be a perfect square. Help him determine the smallest diamond number of N digits.

EXPLANATION:

Hint:
We have to find the smallest number , so we have to first get those numbers by which
we can get a perfect square.After getting the required number of digits we have to arrange them
in increasing order.
If we have to arrange in increasing order why not start placing digits from front and take the next
digit greater or equal to the previously placed digit.

Generate the possible numbers recursively keeping track of following in each recursive step :

  1. position: the current position of the recursive step i.e. which position digit is being placed.
  2. prev: the previous digit placed because the current digit has to be greater than equal to prev.
  3. sum: the sum of squares of digits placed till now. When digits are placed, this will be used to check whether the sum of squares of all digits placed is a perfect square or not.
  4. A vector which stores what all digits have been placed till this position.

If placing a digit at a position and moving to the next recursive step leads to a possible solution then return 1, else backtrack.

TIME COMPLEXITY:

The time complexity is O(sqrt(N)) per test case.

SOLUTION:

SOLUTION:

Editorialist’s Solution

#include <bits/stdc++.h>
using namespace std;

// function to check if
// number is a perfect square
int isSquare(int n)
{
	int k = sqrt(n);
	return (k * k == n);
}

// function to calculate the
// smallest N digit number
int calculate(int pos, int prev,
			int sum, vector<int>& v)
{

	if (pos == v.size())
		return isSquare(sum);

	// place digits greater than equal to prev
	for (int i = prev; i <= 9; i++) {
		v[pos] = i;
		sum += i * i;

		// check if placing this digit leads
		// to a solution then return it
		if (calculate(pos + 1, i, sum, v))
			return 1;

		// else backtrack
		sum -= i * i;
	}
	return 0;
}

string minValue(int n)
{

	vector<int> v(n);
	if (calculate(0, 1, 0, v)) {

		// create a string representing
		// the N digit number
		string answer = "";
		for (int i = 0; i < v.size(); i++)

			answer += char(v[i] + '0');

		return answer;
	}

	else
		return "-1";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int T;
	cin >> T;
	while(T--){
		int n;
		cin>>n;
		cout<<minValue(n)<<endl;
	}

	return 0;
}