C++

問題概要この問題では、ひとつの整数が与えられます。求めるのは、その数を2進表現したときに含まれる「0」の個数と「1」の個数をそれぞれカウントし、2つの値のXOR（排他的論理和）を計算することです。具体例を使って、問題の内容を確認してみましょう。入力n = 9出力0説明binary = 1001 0の個数 = 2 1の個数 = 2 2 ^ 2 = 09を2進数で表すと「1001」になり、「0」が2個、「1」が2個含まれています。そこで 2 XOR 2 = 0 という結果が得られます。解決のためのアプローチこの問題は、次の手順で解くことができます。与えられた数値を2進数として扱い、最下位ビットから

C++プログラミング言語では、論理演算子をキーワード（単語表記）で記述することができます。これらのキーワードは、C言語の時代に「&&」「!」「||」といった記号を入力できないキーボード環境が多かったことから導入されたものです。 現在では、これらはISO C++規格で定義された「代替トークン（alternative tokens）」と呼ばれ、C++では特別なヘッダーをインクルードしなくても常に使用できます。ここでは、C++で使える論理演算子の単語表記について詳しく解説します。 演算子と単語表記の一覧 演算子記号単語表記 論理AND（かつ）&&and 論理OR

ここでは、2つの文字列を比較する際に大文字と小文字の違いを無視するstrcmp(文字列比較)関数を独自に作成します。この関数は、string1 < string2 の場合は -1、string1 = string2 の場合は 0、string1 > string2 の場合は 1 を返します。まず、具体例で問題を確認しましょう。入力string1 = "Hello" , string2 = "hello"出力0アルゴリズムの考え方大文字小文字を無視して文字列を比較する独自のstrcmp関数を作るには、両方の文字列の文字を先頭から順に走査していき

memcpy()関数とはmemcpy()は、指定されたサイズ分のデータをコピー元（source）からコピー先（destination）へ複製するための標準ライブラリ関数です。memcpy関数のプロトタイプは次の通りです。void * memcpy(void *destination_location, void *source_location, size_t size)自作memcpy()の実装ここでは、データを1バイト（1文字）ずつコピー元からコピー先へ順番に転送するシンプルな実装を紹介します。#include<stdio.h> #include<string.h>

C言語およびC++の標準ライブラリに含まれる atoi() 関数は、文字列を整数値に変換するために使用される関数です。文字列を引数として受け取り、対応する整数型の値を返します。構文int atoi(const char string)パラメータと戻り値パラメータ： atoi() 関数は、整数に変換対象となる文字列を入力として受け取ります。戻り値： この関数は整数値を返します。入力された文字列が有効な数値文字列であれば、その整数相当の値が返されます。無効な文字列の場合は 0 が返されます。atoi() の実装の考え方独自の atoi() を実装する際の基本的なアプローチは以下の通りです。まず、文

この問題では、2つの二分木が与えられます。私たちの課題は、この2つの木が同一であるかどうかを判定するコードを書くことです。2つの木が「同一」であるとは、すべての対応するノードが同じ値を持ち、まったく同じ位置（構造・向き）に配置されている状態を指します。例上の2つの木は、各ノードの値も配置位置も完全に一致しているため、同一の木であると言えます。同一性判定の考え方2つの木が同一かどうかを調べるには、両方の木をルートから順番にたどりながら、対応するノード同士を1つずつ比較していきます。比較の途中で値が異なるノードが見つかった場合は、その時点で「同一ではない」と判定して処理を終了します。逆に、すべての

この記事では、2つの整数 x と y が与えられたとき、標準ライブラリの pow(x, y) と同等の結果を返す関数を、反復処理 を用いて O(log y) の時間計算量で実装する方法を解説します。アルゴリズムの考え方単純なべき乗計算をループで行うと、y 回の掛け算が必要となり計算量は O(y) になります。しかし、「繰り返し二乗法（バイナリ累乗法）」と呼ばれる手法を使うと、計算量を O(log y) まで削減できます。基本的なアイデアは次のとおりです。結果を格納する変数 result を 1 で初期化します。y が奇数のときだけ、result に x を掛けます。各反復のたびに、y を半分に

概要本記事では、与えられた整数が3の倍数であるかどうかを判定するC++プログラムの作成方法を解説します。一般的な解法とその課題最もよく知られている方法は、各桁の数字をすべて足し合わせるというものです。桁の合計が3の倍数であれば元の数も3の倍数であり、そうでなければ3の倍数ではありません。この方法は正しく動作しますが、桁ごとの分解と加算が必要なため、必ずしも最も効率的とは言えません。効率的な解法：2進数のビットカウントを利用するより効率的なアプローチは、数値の2進表現におけるセットビット（1になっているビット）の数を利用する方法です。「奇数番目の位置にあるセットビットの数」と「偶数番目の位置にあ

この記事では、符号なし整数 n が与えられたとき、その数値のすべてのビットを反転させた結果の数値を返すプログラムを C++ で作成します。まず、具体例を使って問題を確認しましょう。入力例n = 1出力例2147483648解説1 の2進表現は「000...0001」です。これを反転すると「100...0000」になり、10進数では 2147483648 となります。つまり、最下位ビット(LSB)にあった1が、最上位ビット(MSB)へと移動するイメージです。方法1: ビット位置の公式を使う方法最もシンプルな解法は、各ビットの位置を対応付ける公式を利用する方法です。数値の2進表現に対してループ処理

数値の桁を反転するプログラムとは、数値を構成する各桁の位置を入れ替え、並び順を逆にする処理を行うものです。 例えば、5桁の数値が「abcde」である場合、反転後は「edcba」になります。 それでは、具体的な例を使って問題を理解してみましょう。 入力 n = 786521 出力 125687 数値の桁を反転するには、元の数値の下の桁（1の位）から順に取り出し、反転結果を格納する変数に追加していきます。処理の流れは以下のとおりです。 手順1： n % 10 で最下位桁（1の位）を取り出し、reverseNumber = reverseNumber * 10 + (n % 10) を計算して追

この記事では、与えられた配列または文字列の要素を逆順に並び替えるC++プログラムの作成方法を解説します。配列と文字列はどちらも同じ手順で処理できるため、基本的な考え方を一度覚えれば両方に応用できます。 まず、具体例を使って問題を確認しましょう。 入力例(配列の場合) array = {2, 5, 7, 1, 9} 出力例 {9, 1, 7, 5, 2} 入力例(文字列の場合) string = Hello! 出力例 !olleH 逆順にする仕組み 配列(文字列も同様)を逆順にするには、先頭と末尾の要素を順番に交換していく方法が基本です。具体的には、次の手順で処理を行います。 先頭位置を示す変

本記事では、二分木（バイナリツリー）が与えられたときに、その木の最大の深さ（高さ）を求めるプログラムをC++で作成する方法を解説します。問題の理解まず、具体的な例を使って問題を確認しましょう。上図の二分木の高さは 3 です。アプローチ：再帰による高さの計算木の最大の高さを求める基本的な考え方は次のとおりです。着目しているノードの左部分木と右部分木の高さをそれぞれ求める両者のうち大きい方に1を加えた値が、そのノードを根とする木の高さになるこの処理は再帰的に行われます。木の末端（葉）のノードに到達するまで再帰呼び出しが続き、戻りながら各部分木の高さに1ずつ加算していくことで、最終的に木全体の高さが

この問題では、二分木が与えられ、「再帰」を使って木のサイズを計算するプログラムを作成することが課題となります。 ここでいう木のサイズとは、その木に含まれるノードの総数のことです。 具体例を見ながら問題を理解していきましょう。 上の木の場合、サイズは 5 となります。 解法の考え方：再帰によるサイズ計算 木のサイズを求めるには、左部分木のサイズ + 右部分木のサイズ + 1（現在のノード） を計算します。再帰関数は、木の左右それぞれの部分木に対して呼び出され、部分木が存在しない（NULL の）場合は 0 を返します。 上記の例をこの手法で解いてみる ルート（値3）のサイズを求める場合： si

問題の概要 この記事では、2つの整数 x と n が与えられたときに、pow(x, n)（xのn乗）を計算するC++プログラムの作成方法を解説します。 まず、具体例で問題を確認しましょう。 入力例 x = 5 , n = 3 出力例 125 それでは、pow(x, n) を計算するプログラムを見ていきましょう。 C++での実装例 #include <iostream> using namespace std; float myPow(float x, int y) {     if(y == 0)    &nbs

ここでは、リンクリスト（連結リスト）とインデックスが与えられたときに、リスト内のN番目のノードを取得する関数をC++で実装する方法を解説します。 まず、具体的な例を使って問題を確認しましょう。 入力例 linked list = 34 -> 4 -> 9 -> 1 , n = 2 出力例 9 この場合、インデックス2（0始まり）にあるノードのデータ「9」が出力されます。 解決のアプローチ n番目のノードへアクセスするには、リンクリストの先頭ノードから順にポインタをたどりながらインデックスのカウントを増やしていき、目的のn番目の位置に到達した時点でそのノードのデータを返します

問題概要 この問題では、n個の要素からなる配列が与えられます。配列Aのすべての要素同士のペア（自分自身とのペアも含む）の和を要素とする、サイズ n×n の数列Bを生成し、その数列に含まれるすべての要素のXOR（排他的論理和）を求めて出力するのが課題です。 入出力例 入力 − A = (1, 4, 5) 出力 − 0 説明 − B (1+1, 1+4, 1+5, 4+1, 4+4, 4+5, 5+1, 5+4, 5+5) B (2, 5, 6, 5, 8, 9, 6, 9, 10) すべての値のXOR = 2^5^6^5^8^9^6^9^10 = 0 解法のアプローチ この問題を効率的に解く

問題の概要この問題では、1つの文字列が与えられます。求めるのは、文字列に含まれる各文字のうち出現頻度が素数になっているものだけを取り上げ、それらの頻度のXOR(排他的論理和)を計算して出力することです。具体例を使って問題を確認してみましょう。入力 − TutorialsPoint出力 − 3説明：t … 3回出現(3は素数)u … 2回出現(2は素数)o … 2回出現(2は素数)r … 2回出現(2は素数)i … 2回出現(2は素数)a … 1回出現(1は素数ではない)l … 1回出現(1は素数ではない)s … 1回出現(1は素数ではない)p … 1回出現(1は素数ではない)n … 1回出現(

この問題では、二分木とその木に含まれる2つのノードが与えられます。求めるのは、この2つのノードを結ぶパス上に存在するすべてのノードの値のXOR（排他的論理和）です。 具体例を使って問題を確認しましょう。 1 / \ 6 3 / \ / \ 2 4 7 5 上の二分木において、ノード2からノード3までのパス上の全ノードのXORを求めます。 ノード2からノード3へのパスは「2 → 6 → 1 → 3」です。 この解法では、ルートから各ノードまでの累積XORを利用します。path[2] = 1 ⊕ 6 ⊕ 2 = 5、p

この記事では、n個の要素からなる配列と、配列上の開始位置Lから終了位置Rまでを指定する複数のクエリが与えられたとき、各範囲内に偶数回出現した要素のXORを求める問題をC++で解きます。 問題の例 まず、具体的な入力と出力を見てみましょう。 入力: array = {1, 2, 3, 1, 1, 2, 2, 3} queries = 2 L = 2, R = 5 L = 2, R = 7 出力: 1 0 範囲[2, 5]には {3, 1, 1, 2} が含まれ、「1」だけが2回(偶数回)出現するため答えは1になります。一方、範囲[2, 7]には {3, 1, 1, 2, 2, 3} が含まれ、す

問題の概要この問題では、n個のノードからなる木と、木のノードを指定する複数のクエリが与えられます。目的は、指定されたノードを根とする部分木に含まれるすべてのノードの値のXOR(排他的論理和)を求めて出力することです。具体例を使って問題を理解しましょう。次のような木を考えます。クエリ: {1, 6, 5}出力:0 0 5計算過程:1^6^3^2^4^7^5 = 0 6^2^4 = 0 5 = 5ノード1を根とする部分木は木全体に相当し、そのXORは0になります。同様に、ノード6の部分木(ノード6・2・4)のXORも0、ノード5の部分木はノード5のみなのでXORは5となります。解法アプローチこの問