Editorial - SID

editorial
1

PROBLEM LINK:

Contest

Author: Sumukh Bhardwaj
Tester: Rahul Sharma
Editorialist: Sumukh Bhardwaj

DIFFICULTY:

EASY

PREREQUISITES:

Basic Programming

PROBLEM:

Given a number N keep finding the sum of squares of all the digits of N unless it becomes equals to 1 or the sum repeats.

Return 1 if the number ends at value 1, otherwise, return 0.

QUICK EXPLANATION:

Simulate the process and keep a note of all the sum achieved so far if the sum is repeated return 0 otherwise 1.

EXPLANATION:

There are 2 parts to the algorithm we’ll need to design and code.

  1. Given a number n, what is its next number?
  2. Follow a chain of numbers and detect if we’ve entered a cycle.

Part 1 can be done by using the division and modulus operators to repeatedly take digits off the number until none remain, and then squaring each removed digit and adding them together. Have a careful look at the code for this, “picking digits off one-by-one” is a useful technique you’ll use for solving a lot of different problems.

Part 2 can be done using a HashSet/unordered map. Each time we generate the next number in the chain, we check if it’s already in our HashSet.

  • If it is not in the HashSet, we should add it.
  • If it is in the HashSet, that means we’re in a cycle and so should return false.

The reason we use a HashSet/unoredred_map and not a Vector, List, or Array is because we’re repeatedly checking whether or not numbers are in it. Checking if a number is in a HashSet takes O(1) time, whereas for the other data structures it takes O(n) time. Choosing the correct data structures is an essential part of solving these problems.

COMPLEXITIES

Here N is the number given.

TIme Complexity: O(log N).

Space Complexity: O(log N).

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;

long long find(long long n)
{
long long ans=0;

while(n)
{
	ans+=(n%10)*(n%10);
	n=n/10;
}

return and;
}

long long isHappy(long long n) {

unordered_map<int, int> mark;

while(n != 1 && mark[n] == 0)
{
	mark[n] = 1;
	n = find(n);
}

return n == 1;
}

int main() {
ios_base::sync_with_stdio(false);

long long t,k;

cin>>t;
while(t--)
{
	cin>>k;
	cout<<isHappy(k)<<endl;
}

return 0;
}
1 Like