C++

2つの数値 A と B を掛け合わせた結果を求めたい場合、その積が64ビット整数（long long）の表現範囲を超えてしまうかどうかを事前に確認する必要があります。例えば、100 × 200 のような小さな数値同士の乗算では範囲を超えませんが、10000000000 × -10000000000 のように大きな数値同士を掛け合わせると、結果が64ビット整数の上限・下限を超えてオーバーフローが発生します。このようなオーバーフローを検出するには、以下の手順に従います。オーバーフロー判定の手順どちらか一方の数値が 0 である場合、積は必ず0になるため、オーバーフローは発生しません。それ以外の場合、

本記事では、ある整数が「マジックナンバー」であるかどうかを判定するC++プログラムを紹介します。マジックナンバーとは、各桁の数字を再帰的に合計していき、最終的に1になる数のことです。マジックナンバーとは？例として、50311という数を見てみましょう。50311 → 5 + 0 + 3 + 1 + 1 = 1010 → 1 + 0 = 1このように、桁の合計が最終的に1になれば、その数はマジックナンバーと呼ばれます。判定するには、数が1桁になるまで各桁の合計を繰り返し求める必要があります。C++での実装例#include <iostream> using namespace std;

素数に挟まれた数とは？ 「素数に挟まれた数」とは、ある数値の直前の数と直後の数が、どちらも素数であるような数のことを指します。 例えば 642 の場合を見てみましょう。642の直前の数は 641、直後の数は 643 であり、この2つはどちらも素数です。したがって、642は素数に挟まれている数だと言えます。 判定方法は非常にシンプルです。対象となる数を n としたとき、n-1 と n+1 の両方が素数かどうかを確認するだけで済みます。 アルゴリズムの流れ 判定したい数値 n を入力として受け取る n-1 が素数かどうかを判定する n+1 が素数かどうかを判定する 両方が素数であれば true、

3つの整数 a、b、c が与えられたとき、それぞれの数値から「0」という桁をすべて取り除いた後も、等式 a + b = c が成り立つかどうかを判定する問題を考えてみましょう。 例として、a = 102、b = 130、c = 2005 の場合を見てみます。各数値から0を削除すると、それぞれ 12、13、25 になります。このとき 12 + 13 = 25 が成立するため、答えは「真（true）」となります。 解決のアプローチ 基本的な考え方はシンプルです。 まず、各数値に含まれる0の桁をすべて削除した新しい数値を作成します。 次に、変換後の a と b を足し合わせた結果が、変換後の c

はじめに0と1だけで構成されるバイナリ文字列が与えられたとき、その文字列の中に同じ文字が連続して出現する箇所があるかどうかを判定することを考えます。連続した同じ文字が存在する場合、その文字列は「無効」、存在しない場合は「有効」とみなします。例えば、文字列 101010 は隣り合う文字がすべて異なるため有効ですが、10111010 には 11 という連続部分が含まれるため無効となります。解決のアプローチこの問題は非常にシンプルな手法で解決できます。文字列を左から右へ走査しながら、隣接する2つの文字を順番に比較していきます。一致するペアが1つでも見つかった時点で、連続する同じ文字が存在すると判断で

2つの円(中心座標と半径)が与えられたとき、小さい方の円が大きい方の円の内側に収まっているかどうかを判定する問題について解説します。判定結果は、以下の3つの場合に分けられます。円の位置関係の3つのパターンパターン1:完全に内側にある場合小さい円が大きい円の内部にあり、互いに接触していない状態です。このとき、「2つの中心間の距離 + 小さい円の半径」が「大きい円の半径」より小さくなります。パターン2:内接している場合小さい円が大きい円の内部にあるものの、大きい円の円周に接している状態です。このとき、「2つの中心間の距離 + 小さい円の半径」が「大きい円の半径」と等しくなります。パターン3:一部だ

要素数 n の配列 A が与えられたとき、その配列が「ペアワイズソート（pairwise sorted）」されているかどうかを判定します。ペアワイズソートとは、隣接する2つの要素からなるペアごとに昇順に並んでいる状態を指します。例えば、配列が {8, 10, 18, 20, 5, 15} の場合を考えてみましょう。この配列は (8, 10)、(18, 20)、(5, 15) という3つのペアに分けられます。それぞれのペア内で前の要素が後の要素以下になっているため、この配列はペアワイズソートされていると判断できます。なお、配列の要素数が奇数の場合、最後の1つの要素はペアを形成できないため無視され

この記事では、C++を使って与えられた行列が「スパース行列（疎行列）」かどうかを判定する方法を解説します。スパース行列とは、行列の要素の大部分が0で占められている行列のことです。一般的な定義では、全要素の3分の2以上が0である場合、その行列はスパース行列とみなされます。以下にスパース行列の例を示します。 判定方法は非常にシンプルです。まず行列内にある0の個数を数え、その数が全要素数の3分の2より大きければ、その行列はスパース行列であると判断します。 サンプルコード #include <iostream> #include <cmath> #define MAX 5

この記事では、与えられた数値がスパース数（sparse number）であるかどうかを判定する方法を解説します。スパース数とは？スパース数とは、その数値を2進数で表したときに、「1」が2つ以上連続して現れない数のことを指します。例として、数値 72 を考えてみましょう。72を2進数で表すと 01001000 となります。この2進表現には連続する「1」が存在しないため、72はスパース数であるといえます。判定アルゴリズムの考え方スパース数の判定は、ビット演算を使うと非常にシンプルに行えます。手順は以下の通りです。対象の数値を n としたとき、1. n を右に1ビットシフトします。2. 元の n と

回文の回転とは回文（パリンドローム）とは、前から読んでも後ろから読んでも同じになる文字列のことです。本記事では、ある文字列が「回文を回転させたもの」になっているかどうかをC++で判定する方法を解説します。例えば「AAAAD」という文字列は、そのままでは回文ではありません。しかし、これを1文字ずつ回転させていくと「AADAA」となり、これは回文です。このように、元の文字列自体は回文でなくても、適切な位置まで回転させることで回文になるケースが存在します。判定アルゴリズムの考え方文字列が回文の回転であるかを確認するには、以下の手順を実行します。まず、現在の文字列が回文かどうかをチェックします。回文で

ある整数 n が与えられたとき、それを2つの過剰数の和として表現できるかどうかを判定します。表現できる場合はその2つの数を出力し、できない場合は -1 を出力します。 ここで「過剰数（Abundant Number）」とは、その数自身を除く約数（真の約数）の総和 sum(n) が、元の数の値より大きくなるような数のことです。例えば 12 の真の約数は 1, 2, 3, 4, 6 で、その総和は 16 となり 12 より大きいため、12 は過剰数です。 解法のアプローチ この問題を解くには、まず N 未満のすべての過剰数をあらかじめセット（set）に格納しておきます。次に、与えられた数 n に

整数 n が与えられたとき、その2進表現が「101010…」のように0と1が交互に並ぶパターン（交互パターン）になっているかどうかを判定する方法を紹介します。 基本的なアプローチ 考え方は非常にシンプルです。数値を2進数として下位ビットから順に調べていき、隣り合う2つのビットが同じ値だった時点で false を返します。最後まで隣接ビットが一度も一致しなければ、その数は交互パターンを持っていると判断できます。 n % 2 で最下位ビットを取得し、直前のビット（previous）として保存する n / 2 で数値を1ビット右にずらす 新しい最下位ビット（current）と直前のビットを比較

はじめにある整数 n が与えられたとき、その2進表現が「交互パターン」になっているかどうかを判定する問題を考えてみましょう。ここでいう交互パターンとは、101010… や 0101… のように、1と0が交互に並んでいるビット列のことです。本記事では、シフト演算とXORを組み合わせることで、定数時間 O(1) でこの判定を行うエレガントな手法を紹介します。アルゴリズムの考え方ポイントとなるのは次の計算です。num = n XOR (n >> 1)n が交互パターンであれば、隣り合うビット同士は必ず異なる値になります。そこで、n を1ビット右シフトしたものとXORを取ると、各ビット位置

クリシュナムルティ数とはクリシュナムルティ数（Krishnamurty Number）とは、各桁の数字の階乗の合計が元の数そのものと等しくなる特別な数のことです。例えば、145という数値を見てみましょう。1! + 4! + 5! = 1 + 24 + 120 = 145 となり、各桁の階乗の合計が元の数と一致します。したがって、145はクリシュナムルティ数です。この性質を持つ数は非常に珍しく、代表的な例としては 1、2、145、40585 などが挙げられます。判定アルゴリズムの考え方判定ロジックはシンプルで、以下の手順で処理を行います。対象の数値から一桁ずつ数字を取り出す取り出した数字それぞれ

本記事では、与えられた数値が23で割り切れるかどうかを判定するC++プログラムを紹介します。例えば、1191216という数値は23で割り切れることが知られています。この割り切り判定を行うには、以下のルールに従います。毎回、数値（桁を削った数）から末尾の一桁を取り出します。取り出した末尾の一桁に7を掛けた値を、桁を削った残りの数に加算します。必要な範囲でこれらの手順を繰り返します。実際に17043という数値で確認してみましょう。17043 の場合 → 1704 + 7 × 3 = 1725 1725 の場合 → 172 + 7 × 5 = 207 207 は 9 × 23 なので、17043 は

本記事では、与えられた数値が41で割り切れるかどうかを判定するC++プログラムを紹介します。例として、104413920565933という大きな数値を取り上げます。この数値は実は41で割り切れます。巨大な数値を実際に割り算せずに判定するには、次の「41の倍数判定法」を利用します。41で割り切れるかの判定ルール元の数（または切り捨て後の数）から、末尾の一桁を取り出す。残りの数（末尾を切り捨てた数）から、「4 × 取り出した一桁」を引く。必要な限り、この手順を繰り返す。最終的に得られた小さな数が41の倍数であれば、元の数も41で割り切れることになります。これは「10a + b が41の倍数 ⟺ a

本記事では、与えられた数値や文字列が「1」「14」「144」のみを連結した形になっているかどうかを判定する問題を解説します。例えば、文字列「111411441」はこれらの数字の組み合わせで表現できるため有効ですが、「144414」はどの組み合わせでも表現できないため無効となります。アルゴリズムの考え方判定方法は非常にシンプルです。以下の手順で処理を行います。まず、数値の末尾から1桁・2桁・3桁ずつ数字を取り出し、それが「1」「14」「144」のいずれかに一致するかを確認します。一致するパターンが見つかったら、その桁数に対応する数（10・100・1000）で数値を割り、残りの部分に対して同じ処理

配列Aと整数Kが与えられたとき、Kの倍数と次の倍数の「間」に挟まれた要素だけをソートすることを考えます。例えば、配列Aが [2, 13, 3, 1, 21, 7, 8, 13, 12]、K = 2 の場合、期待される出力は [2, 1, 3, 7, 13, 21, 8, 13, 12] です。ここで2の倍数は 2・8・12 の3つです。最初の倍数2と次の倍数8の間にある 13, 3, 1, 21, 7 は昇順に並べ替えて 1, 3, 7, 13, 21 とし、8と12の間には要素13しかないため、すでに整列済みとしてそのまま残します。 アルゴリズムの考え方 配列を先頭から順に走査し、Kの倍数

問題の概要文字列の配列と、ソートの基準となるもう一つの文字列が与えられているとします。基準文字列に含まれる文字の出現順序を「独自のアルファベット順」とみなし、その順序に従って文字列の配列を並べ替えます。ここでは、配列内の文字列も基準文字列もすべて小文字で構成されているものと仮定します。例えば、文字列の配列が [hello, programming, science, computer, india]、基準文字列が pigvxbskyhqzelutoacfjrndmw である場合、ソート後の出力は [programming, india, science, hello, computer] とな

2つの異なる配列があるとします。C++ STLのpairクラスを利用すると、一方の配列の値を基準にして、もう一方の配列を連動させてソートすることができます。例えば、A1 = [2, 1, 5, 4, 9, 3, 6, 7, 10, 8]、A2 = [A, B, C, D, E, F, G, H, I, J] という2つの配列を用意した場合、実行結果は次のようになります。A1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]A2 = [B, A, F, D, C, G, H, J, E, I]基本的な考え方ここではC++ STLのpair（ペア）を使用します。A1の要素をfir