ハッピー数


難易度 簡単に
よく聞かれる Adobe Amazon (アマゾン) Apple JPモルガン
ハッシュ ハッシング 数学

問題文

ハッピー数とは何ですか?

このプロセスに従って特定の数を1に減らすことができれば、数はハッピー数です。

->指定された数の桁のXNUMX乗の合計を求めます。 この合計を古い数値に置き換えます。 数をXNUMXつに減らすことができるか、それがサイクルを形成するまで、このプロセスを繰り返します。

つまり、数字から始めて、それをXNUMXに変換するプロセスをたどったかのようにサイクルが形成されますが、私たちが見つめた数に達したので、それはサイクルを形成していると言います。

数形成サイクルの例は次のとおりです。

89
8*8+9*9=145
1*1*+4*4+5*5=42
4*4+2*2=20
2*2+0*0=4
4*4=16
1*1+6*6=37
3*3+7*7=58
5*5+8*8=89

したがって、これはサイクルを形成します。 したがって、毎回1を形成し続けるため、これを89に減らすことはできないため、ハッピー数ではありません。 数が1に減った場合はtrueを返し、そうでない場合はfalseを返します。

19
true

説明

1^2+9^2=82

8^2+2^2=68

6^2+8^2=100

1^2+0^2+0^2=1

ハッピー数

この数をXNUMXに減らすことができるので、ハッピー数になります。

アプローチ

この問題は非常に単純で、セットの基本概念のみを使用します。

セットとは?

セットは、固有の要素が存在する連想コンテナです。

この問題を解決するために、 セッションに。 セットでは、数字のXNUMX乗を足した後、新しく形成された数字を挿入します。 要素がすでにセットに存在する場合、それはループを形成していることを意味し、指定された数をXNUMXに変換できないため、これはハッピー数ではありません。 数がXNUMXに減った場合、指定された数はハッピー数です。

コード

ハッピー数のC ++コード

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

 bool isHappy(int n) {
        unordered_set<int> tmp;
        while(n != 1)
        {
            if(tmp.find(n) == tmp.end())
                tmp.insert(n);
            else
                return false;
            int sum = 0;
            while(n != 0)
            {
                sum += pow(n % 10,2);
                n = n / 10;
            }
            n = sum;
        }
        return true;
    }

int main() 
{ 
    int n=19;
    int answer=isHappy(n);
    if(answer)
    cout<<"true"<<endl;
    else
    cout<<"false"<<endl;
  return 0; 
}
true

ハッピー数のJavaコード

import java.util.*;

class Main
{
  static public boolean isHappy(int n) {
      Set<Integer> inLoop = new HashSet<Integer>();
      int squareSum,remain;
      while (inLoop.add(n)) {
      	squareSum = 0;
        while (n > 0) {
            remain = n%10;
          squareSum += remain*remain;
          n /= 10;
        }
        if (squareSum == 1)
          return true;
        else
          n = squareSum;
    }
    return false;
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int n = 19;
    boolean result = isHappy(n);
    System.out.print(result);
  }
}
19
true

複雑さの分析

時間の複雑さ

O(log N)、 log Nの基数は10です。したがって、時間計算量は数値の桁数に依存します。 そして、それは対数係数とともに減少し続けます。 したがって、時間計算量はO(log N)です。

スペースの複雑さ

O(logN)、 これらの中間番号を格納するにはスペースが必要です。 時間計算量と同様に、空間計算量も対数です。