Reverse Game

source: University of Electro-Communications Programming Contest 2013

raw_problem:
Problem I: Reverse Game

あるところにオセロが趣味な女の子がいました。時間があるときに家族とオセロを楽しんでいます。

ある日、女の子はいつものようにオセロで遊ぼうとしました。ところが、みんな忙しくて誰も遊んでくれませんでした。
そこでオセロのボードとこまを使って１人で遊べるゲームを考え出しました。

問題

縦\( R \)マス、横\( C \)マスのマス目全てにオセロの駒が上面が黒あるいは白になるように配置されている。

以下の図のように「あるマスを選んで、その上下左右斜め方向にある駒を全て裏返す」という操作を繰り返し行うことを考える。
全ての駒の上面を白にするような操作の仕方の個数を求めよ。 ただし、以下の条件を満たす必要がある。

同じマスに二度操作を行うことはできない

操作の順序は区別しない

全ての駒の上面が白になってから操作を続けることは可能である

入力

1行目に整数\( R \)と整数\( C \)がそれぞれ空白区切りで与えられる。

続けて\( R \)行に、それぞれ\( C \)個の整数値(0か1)が与えられる。\( r \)行目の\(
c \)個目の整数は、マス目(r,c)の状態を表す。

1は上面が黒であることを、0は上面が白であることを表す。

出力

盤面の全ての駒の上面を白にすることができるなら、そのような操作の仕方の個数を\(
1000000009 (= 10 ^ 9 + 9) \)で割った余りを1行に出力せよ。

盤面の全ての駒の上面を白にすることができないなら、\( 0 \)と1行に出力せよ。

制約

\(1 \leq R \leq 50, 1 \leq C \leq 50\)

サンプル入出力

入力1

1 3
1 1 1

出力1

4

\( \{(1,1)\}, \{(1,2)\}, \{(1,3)\}, \{(1,1),(1,2),(1,3)\} \)の4通りである。

入力2

1 3
1 0 1

出力2

0

入力3

2 4
0 1 0 1
1 0 1 0

出力3

1

solutions: ["R, C = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(R)]\nMOD = 10**9+9\n\n\ndef num(x, y):\n    return x*C+y\n\n\ndef reverse_num(x, y):\n    v = 0\n    for i in range(R):\n        v |= 1 << num(i, y)\n    for j in range(C):\n        v |= 1 << num(x, j)\n    for k in range(R):\n        l = y-x+k\n        if not 0 <= l < C:\n            continue\n        v |= 1 << num(k, l)\n    for k in range(R):\n        l = y+x-k\n        if not 0 <= l < C:\n            continue\n        v |= 1 << num(k, l)\n    return v\n\n\nN = R*C\nbase = [0]*N\nrank = 0\nfor i in range(R):\n    for j in range(C):\n        v = reverse_num(i, j)\n        for k in range(N-1, -1, -1):\n            if (v >> k) & 1:\n                v ^= base[k]\n        if v == 0:\n            continue\n        rank += 1\n        l = v.bit_length()-1\n        base[l] = v\n        for k in range(l+1, N):\n            if (base[k] >> l) & 1:\n                base[k] ^= v\n\nv = 0\nfor i in range(R):\n    for j in range(C):\n        if A[i][j]:\n            v |= 1 << num(i, j)\n\nfor k in range(N-1, -1, -1):\n    if (v >> k) & 1:\n        v ^= base[k]\nif v:\n    print(0)\nelse:\n    print(pow(2, N-rank, MOD))\n\n"]

source: aizu

question:
Problem I: Reverse Game

In a certain place, there was a girl whose hobby was playing Othello. She enjoys playing Othello with her family whenever she has the time.

One day, as usual, the girl tried to play Othello. However, everyone was busy and nobody could play with her.
So she came up with a game that could be played alone using the Othello board and pieces.
Problem

All the Othello pieces are arranged on a grid with \( R \) rows and \( C \) columns, with the top surface of each piece being either black or white.

Consider performing the following operation repeatedly, as shown in the figure below: "Choose a square and flip all the pieces in the vertical, horizontal, and diagonal directions based on that square."
Find the number of ways to perform the operations such that the top surface of all the pieces becomes white. However, the following conditions must be satisfied:

- The same square cannot be operated on twice
- The order of operations does not matter
- Continuing to operate after all the pieces have become white is allowed

![image](1.png)
Input
On the first line, the integer \( R \) and the integer \( C \) are given, separated by a space.
Then, for \( R \) lines, \( C \) integers (either 0 or 1) are given. The integer at the \( r \)-th row and \( c \)-th column represents the state of the square (r,c).
1 indicates that the top surface is black, while 0 indicates that the top surface is white.
Output
If it is possible to turn the top surface of all the pieces on the board white, output the number of such arrangements modulo \(
1000000009 (= 10 ^ 9 + 9) \) on one line.
If it is not possible to turn the top surface of all pieces on the board white, output \( 0 \) on one line.
Constraints

- \(1 \leq R \leq 50, 1 \leq C \leq 50\)

Sample Input/Output
Input 1

```
1 3
1 1 1
```

Output 1

```
4
```

There are 4 ways: \( \{(1,1)\}, \{(1,2)\}, \{(1,3)\}, \{(1,1),(1,2),(1,3)\} \).

Input 2

```
1 3
1 0 1
```

Output 2

```
0
```

Input 3

```
2 4
0 1 0 1
1 0 1 0
```

Output 3

```
1
```

data_split: test


solutions: ["class Solution:\n\n\tdef findReplaceString(self, s: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n\t\tl = []\n\t\tfor (i, tgt, rpl) in zip(indexes, sources, targets):\n\t\t\tif s[i:i + len(tgt)] == tgt:\n\t\t\t\tl.append((i, tgt, rpl))\n\t\tl.sort()\n\t\tj = 0\n\t\ts = list(s)\n\t\tfor (i, tgt, rpl) in l:\n\t\t\ts[i + j:i + j + len(tgt)] = rpl\n\t\t\tj += len(rpl) - len(tgt)\n\t\treturn ''.join(s)\n", "class Solution:\n\n\tdef findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n\t\tsources_dict = {}\n\t\ttargets_dict = {}\n\t\tfor (i, pos_index) in enumerate(indexes):\n\t\t\tsources_dict[pos_index] = sources[i]\n\t\t\ttargets_dict[pos_index] = targets[i]\n\t\tindexes.sort(reverse=True)\n\t\tfor pos_index in indexes:\n\t\t\tsource = sources_dict[pos_index]\n\t\t\ttarget = targets_dict[pos_index]\n\t\t\ttmp_str = S[pos_index:pos_index + len(source)]\n\t\t\tif tmp_str == source:\n\t\t\t\tS = S[:pos_index] + target + S[pos_index + len(source):]\n\t\treturn S\n", "class Solution:\n\n\tdef findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n\t\tfor (i, s, t) in sorted(zip(indexes, sources, targets), reverse=True):\n\t\t\tif S[i:i + len(s)] == s:\n\t\t\t\tS = S[:i] + t + S[i + len(s):]\n\t\treturn S\n", "class Solution:\n\n\tdef findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n\t\t(result, offset) = (S, 0)\n\t\tfor (i, s, t) in sorted(zip(indexes, sources, targets)):\n\t\t\tif S[i:i + len(s)] == s:\n\t\t\t\tresult = result[:offset + i] + t + result[offset + i + len(s):]\n\t\t\t\toffset += len(t) - len(s)\n\t\treturn result\n", "class Solution:\n\n\tdef findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n\t\ts_dict = {}\n\t\tt_dict = {}\n\t\tfor (i, index) in enumerate(indexes):\n\t\t\ts_dict[index] = sources[i]\n\t\t\tt_dict[index] = targets[i]\n\t\tindexes.sort(reverse=True)\n\t\tfor index in indexes:\n\t\t\tsour = s_dict[index]\n\t\t\ttarg = t_dict[index]\n\t\t\tle_s = len(sour)\n\t\t\ttmp_str = S[index:index + le_s]\n\t\t\tif tmp_str == sour:\n\t\t\t\tS = S[:index] + targ + S[index + le_s:]\n\t\treturn S\n", "class Solution:\n\n\tdef findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n\t\tS = list(S)\n\t\tfor (i, s, t) in sorted(zip(indexes, sources, targets), reverse=True):\n\t\t\tappl = all([i + ind < len(S) and S[i + ind] == s[ind] for ind in range(len(s))])\n\t\t\tif appl:\n\t\t\t\tS[i:i + len(s)] = list(t)\n\t\treturn ''.join(S)\n", "class Solution:\n\n\tdef findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n\t\tindex_position = dict()\n\t\tr_list = []\n\t\tfor (pos, index) in enumerate(indexes):\n\t\t\tsource_len = len(sources[pos])\n\t\t\tif S[index:index + source_len] == sources[pos]:\n\t\t\t\tindex_position[index] = pos\n\t\tnext_index = 0\n\t\tfor i in range(len(S)):\n\t\t\tif i < next_index:\n\t\t\t\tcontinue\n\t\t\tif i in index_position:\n\t\t\t\tpos = index_position[i]\n\t\t\t\tr_list.append(targets[pos])\n\t\t\t\tnext_index += len(sources[pos])\n\t\t\telse:\n\t\t\t\tr_list.append(S[i])\n\t\t\t\tnext_index += 1\n\t\treturn ''.join(r_list)\n", "class Solution:\n\n\tdef findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n\t\tidx_og = 0\n\t\tidx_res = 0\n\t\tres = S\n\t\tfor (index, source, target) in sorted(zip(indexes, sources, targets)):\n\t\t\tif S[index:index + len(source)] == source:\n\t\t\t\tindex2 = index - idx_og + idx_res\n\t\t\t\tres = res[:index2] + target + res[index2 + len(source):]\n\t\t\t\tidx_og = index + len(source)\n\t\t\t\tidx_res = index2 + len(target)\n\t\treturn res\n", "class Solution:\n\n\tdef check_source(self, start_idx, s, source):\n\t\ti = 0\n\t\twhile i < len(source):\n\t\t\tif start_idx == len(s):\n\t\t\t\treturn False\n\t\t\tif source[i] != s[start_idx]:\n\t\t\t\treturn False\n\t\t\tstart_idx += 1\n\t\t\ti += 1\n\t\treturn True\n\n\tdef findReplaceString(self, s: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n\t\tres = []\n\t\ti = 0\n\t\twhile i < len(s):\n\t\t\tif i in indexes:\n\t\t\t\tidx = indexes.index(i)\n\t\t\t\tsource = sources[idx]\n\t\t\t\ttarget = targets[idx]\n\t\t\t\tif self.check_source(i, s, source):\n\t\t\t\t\ti += len(source)\n\t\t\t\t\tres.append(target)\n\t\t\t\t\tcontinue\n\t\t\tres.append(s[i])\n\t\t\ti += 1\n\t\treturn ''.join(res)\n"]

starter_code:
class Solution:
    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:

source: leetcode

tags: ['String algorithms', 'Sorting', 'Data structures']

skill_types: ['Sorting', 'Data structures']

raw_problem:
You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.

To complete the ith replacement operation:

Check if the substring sources[i] occurs at index indices[i] in the original string s.

If it does not occur, do nothing.

Otherwise if it does occur, replace that substring with targets[i].

For example, if s = "abcd", indices[i] = 0, sources[i] = "ab", and targets[i] = "eee", then the result of this replacement will be "eeecd".

All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.

For example, a testcase with s = "abc", indices = [0, 1], and sources = ["ab","bc"] will not be generated because the "ab" and "bc" replacements overlap.

Return the resulting string after performing all replacement operations on s.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"
Explanation:
"a" occurs at index 0 in s, so we replace it with "eee".
"cd" occurs at index 2 in s, so we replace it with "ffff".

Example 2:

Input: s = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation:
"ab" occurs at index 0 in s, so we replace it with "eee".
"ec" does not occur at index 2 in s, so we do nothing.

Constraints:

1 <= s.length <= 1000

k == indices.length == sources.length == targets.length

1 <= k <= 100

0 <= indexes[i] < s.length

1 <= sources[i].length, targets[i].length <= 50

s consists of only lowercase English letters.

sources[i] and targets[i] consist of only lowercase English letters.

question:
You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.
To complete the i^{th} replacement operation:

- Check if the substring sources[i] occurs at index indices[i] in the original string s.
- If it does not occur, do nothing.
- Otherwise if it does occur, replace that substring with targets[i].

For example, if s = "abcd", indices[i] = 0, sources[i] = "ab", and targets[i] = "eee", then the result of this replacement will be "eeecd".
All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.

- For example, a testcase with s = "abc", indices = [0, 1], and sources = ["ab","bc"] will not be generated because the "ab" and "bc" replacements overlap.

Return the resulting string after performing all replacement operations on s.
A substring is a contiguous sequence of characters in a string.

Example 1:
![image](1.png)

Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"
Explanation:
"a" occurs at index 0 in s, so we replace it with "eee".
"cd" occurs at index 2 in s, so we replace it with "ffff".

Example 2:
![image](2.png)

Input: s = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation:
"ab" occurs at index 0 in s, so we replace it with "eee".
"ec" does not occur at index 2 in s, so we do nothing.

Constraints:

- 1 <= s.length <= 1000
- k == indices.length == sources.length == targets.length
- 1 <= k <= 100
- 0 <= indexes[i] < s.length
- 1 <= sources[i].length, targets[i].length <= 50
- s consists of only lowercase English letters.
- sources[i] and targets[i] consist of only lowercase English letters.

image_tags: Patterns Patterns

data_split: test


K. Kingdom Partition

problem_index: K

time_limit: 3 seconds

memory_limit: 512 megabytes

note:
The following picture illustrates the example. Adrian and Beatrice don't pay for the dashed roads, they pay $$$2l$$$ for the bold roads, and $$$l$$$ for the solid roads.
So the total cost is $$$2 \cdot 5 + 3 + 3 = 16$$$.
The castles of Adrian and Beatrice are located in bold towns.
![image](images/cf_1666_K/1.png)

source: codeforces

raw_problem:
K. Kingdom Partition

time limit per test
3 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

The King is gone. After the King's rule, all the roads in the Kingdom are run down and need repair. Three of the King's children, Adrian, Beatrice and Cecilia, are dividing the Kingdom between themselves.

Adrian and Beatrice do not like each other and do not plan to maintain any relations between themselves in the future. Cecilia is on good terms with both of them. Moreover, most of the Kingdom's workers support Cecilia, so she has better resources and more opportunity to repair the infrastructure and develop the economy.

Cecilia proposes to partition the Kingdom into three districts: A (for Adrian), B (for Beatrice), and C (for Cecilia), and let Adrian and Beatrice to negotiate and choose any towns they want to be in their districts, and agree on how they want to partition the Kingdom into three districts.

Adrian's castle is located in town $$$a$$$, and Beatrice's one is located in town $$$b$$$. So Adrian and Beatrice want their castles to be located in districts A and B, respectively. Cecilia doesn't have a castle, so district C can consist of no towns.

There is an issue for Adrian and Beatrice. When they choose the towns, they will have to pay for the roads' repair.

The cost to repair the road of length $$$l$$$ is $$$2l$$$ gold. However, Adrian and Beatrice don't have to bear all the repair costs. The repair cost for the road of length $$$l$$$ that they bear depends on what towns it connects:

 For a road between two towns inside district A, Adrian has to pay $$$2l$$$ gold;

 For a road between two towns inside district B, Beatrice has to pay $$$2l$$$ gold;

 For a road between towns from district A and district C, Adrian has to pay $$$l$$$ gold, Cecilia bears the remaining cost;

 For a road between towns from district B and district C, Beatrice has to pay $$$l$$$ gold, Cecilia bears the remaining cost.

The roads that connect towns from district A and district B won't be repaired, since Adrian and Beatrice are not planning to use them, so no one pays for them. Cecilia herself will repair the roads that connect the towns inside district C, so Adrian and Beatrice won't bear the cost of their repair either.

Adrian and Beatrice want to minimize the total cost they spend on roads' repair. Find the cheapest way for them to partition the Kingdom into three districts.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ — the number of towns and the number of roads in the Kingdom ($$$2 \le n \le 1000$$$; $$$0 \le m \le 2000$$$).

The second line contains two integers that represent town $$$a$$$ and town $$$b$$$ — the towns that have to be located in district A and district B, respectively ($$$1 \le a, b \le n$$$; $$$a \ne b$$$).

The following $$$m$$$ lines describe the Kingdom roads. The $$$i$$$-th of them consists of three integers $$$u_i$$$, $$$v_i$$$, and $$$l_i$$$ representing a road of length $$$l_i$$$ between towns $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$; $$$1 \le l_i \le 10^9$$$).

Each pair of towns is connected with at most one road.

Output

In the first line output a single integer — the minimum total cost of roads' repair for Adrian and Beatrice.

In the second line output a string consisting of $$$n$$$ characters 'A', 'B', and 'C', $$$i$$$-th of the characters representing the district that the $$$i$$$-th town should belong to.

If several cheapest ways to partition the Kingdom exist, print any of them.

Example

Input

6 7
1 3
1 2 10
2 3 5
1 3 7
4 5 3
3 6 100
4 6 3
5 6 8

Output

16
ABBCBA

Note

The following picture illustrates the example. Adrian and Beatrice don't pay for the dashed roads, they pay $$$2l$$$ for the bold roads, and $$$l$$$ for the solid roads.

So the total cost is $$$2 \cdot 5 + 3 + 3 = 16$$$.

The castles of Adrian and Beatrice are located in bold towns.

question:
The King is gone. After the King's rule, all the roads in the Kingdom are run down and need repair. Three of the King's children, Adrian, Beatrice and Cecilia, are dividing the Kingdom between themselves.
Adrian and Beatrice do not like each other and do not plan to maintain any relations between themselves in the future. Cecilia is on good terms with both of them. Moreover, most of the Kingdom's workers support Cecilia, so she has better resources and more opportunity to repair the infrastructure and develop the economy.
Cecilia proposes to partition the Kingdom into three districts: A (for Adrian), B (for Beatrice), and C (for Cecilia), and let Adrian and Beatrice to negotiate and choose any towns they want to be in their districts, and agree on how they want to partition the Kingdom into three districts.
Adrian's castle is located in town $$$a$$$, and Beatrice's one is located in town $$$b$$$. So Adrian and Beatrice want their castles to be located in districts A and B, respectively. Cecilia doesn't have a castle, so district C can consist of no towns.
There is an issue for Adrian and Beatrice. When they choose the towns, they will have to pay for the roads' repair.
The cost to repair the road of length $$$l$$$ is $$$2l$$$ gold. However, Adrian and Beatrice don't have to bear all the repair costs. The repair cost for the road of length $$$l$$$ that they bear depends on what towns it connects:
 -  For a road between two towns inside district A, Adrian has to pay $$$2l$$$ gold; -  For a road between two towns inside district B, Beatrice has to pay $$$2l$$$ gold; -  For a road between towns from district A and district C, Adrian has to pay $$$l$$$ gold, Cecilia bears the remaining cost; -  For a road between towns from district B and district C, Beatrice has to pay $$$l$$$ gold, Cecilia bears the remaining cost. The roads that connect towns from district A and district B won't be repaired, since Adrian and Beatrice are not planning to use them, so no one pays for them. Cecilia herself will repair the roads that connect the towns inside district C, so Adrian and Beatrice won't bear the cost of their repair either.
Adrian and Beatrice want to minimize the total cost they spend on roads' repair. Find the cheapest way for them to partition the Kingdom into three districts.

Input
The first line contains two integers $$$n$$$ and $$$m$$$ — the number of towns and the number of roads in the Kingdom ($$$2 \le n \le 1000$$$; $$$0 \le m \le 2000$$$).
The second line contains two integers that represent town $$$a$$$ and town $$$b$$$ — the towns that have to be located in district A and district B, respectively ($$$1 \le a, b \le n$$$; $$$a \ne b$$$).
The following $$$m$$$ lines describe the Kingdom roads. The $$$i$$$-th of them consists of three integers $$$u_i$$$, $$$v_i$$$, and $$$l_i$$$ representing a road of length $$$l_i$$$ between towns $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$; $$$1 \le l_i \le 10^9$$$).
Each pair of towns is connected with at most one road.

Output
In the first line output a single integer — the minimum total cost of roads' repair for Adrian and Beatrice.
In the second line output a string consisting of $$$n$$$ characters 'A', 'B', and 'C', $$$i$$$-th of the characters representing the district that the $$$i$$$-th town should belong to.
If several cheapest ways to partition the Kingdom exist, print any of them.

Example
Input
6 7
1 3
1 2 10
2 3 5
1 3 7
4 5 3
3 6 100
4 6 3
5 6 8

Output
16
ABBCBA

Note
The following picture illustrates the example. Adrian and Beatrice don't pay for the dashed roads, they pay $$$2l$$$ for the bold roads, and $$$l$$$ for the solid roads.
So the total cost is $$$2 \cdot 5 + 3 + 3 = 16$$$.
The castles of Adrian and Beatrice are located in bold towns.
 ![image](1.png)

data_split: test


solutions: ["class Solution:\n\n\tdef grayToBinary(self, n: int) -> int:\n\t\tbinary = n\n\t\twhile n > 0:\n\t\t\tn >>= 1\n\t\t\tbinary ^= n\n\t\treturn binary\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tb = 0\n\t\twhile n > 0:\n\t\t\tb = b ^ n\n\t\t\tn = n >> 1\n\t\treturn b\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tres = n\n\t\twhile n > 0:\n\t\t\tn >>= 1\n\t\t\tres ^= n\n\t\treturn res\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tb = 0\n\t\tfor i in iter(int, 1):\n\t\t\tif n > 0:\n\t\t\t\tb = b ^ n\n\t\t\t\tn = n >> 1\n\t\t\telse:\n\t\t\t\tbreak\n\t\treturn b\n", "class Solution:\n\n\tdef grayToBinary(self, n: int) -> int:\n\t\tmask = n\n\t\twhile mask != 0:\n\t\t\tmask >>= 1\n\t\t\tn ^= mask\n\t\treturn n\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tans = n\n\t\twhile n > 0:\n\t\t\tn = n >> 1\n\t\t\tans = ans ^ n\n\t\treturn ans\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tgray_rep = bin(n)[2:]\n\t\tbinary = gray_rep[0]\n\t\tfor i in range(1, len(gray_rep)):\n\t\t\tif gray_rep[i] == '0':\n\t\t\t\tbinary += binary[i - 1]\n\t\t\telse:\n\t\t\t\tbinary += str(int(not int(binary[i - 1])))\n\t\treturn int(binary, 2)\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tc = 0\n\t\twhile n:\n\t\t\tc ^= n\n\t\t\tn >>= 1\n\t\treturn c\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tbinary = n & 1 << len(bin(n)) - 3\n\t\tfor i in range(len(bin(n)) - 4, -1, -1):\n\t\t\tbinary |= (binary >> 1 ^ n & 1 << i) & 1 << i\n\t\treturn binary\n", "import math\n\nclass Solution:\n\n\tdef grayToBinary(self, n):\n\t\tt = n\n\t\twhile t != 0:\n\t\t\tt = t >> 1\n\t\t\tn = n ^ t\n\t\treturn n\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tv = 0\n\t\twhile n:\n\t\t\tv = v ^ n\n\t\t\tn = n >> 1\n\t\treturn v\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\ta = n >> 1\n\t\twhile a:\n\t\t\tn ^= a\n\t\t\ta = a >> 1\n\t\treturn n\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tk = len(bin(n)) - 2\n\t\tbin_y = 0\n\t\txor = n >> k & 1\n\t\tbin_y = bin_y + xor\n\t\tk = k - 1\n\t\twhile k >= 0:\n\t\t\txor = xor ^ n >> k & 1\n\t\t\tbin_y = bin_y + (xor << k)\n\t\t\tk = k - 1\n\t\treturn bin_y\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tN = n\n\t\twhile n > 0:\n\t\t\tn = n >> 1\n\t\t\tN = N ^ n\n\t\treturn N\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tx = 0\n\t\twhile n > 0:\n\t\t\tx = x ^ n\n\t\t\tn = n >> 1\n\t\treturn x\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\ttemp = n\n\t\twhile n > 0:\n\t\t\tn >>= 1\n\t\t\ttemp = temp ^ n\n\t\treturn temp\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tinv = 0\n\t\twhile n:\n\t\t\tinv = inv ^ n\n\t\t\tn = n >> 1\n\t\treturn inv\n\t\treturn n ^ n >> 1\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tr = n\n\t\tn >>= 1\n\t\twhile n:\n\t\t\tr ^= n\n\t\t\tn >>= 1\n\t\treturn r\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tresult = n\n\t\twhile n > 0:\n\t\t\tn = n >> 1\n\t\t\tresult ^= n\n\t\treturn result\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tcount = 0\n\t\twhile n:\n\t\t\tcount ^= n\n\t\t\tn >>= 1\n\t\treturn count\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tdiv = n\n\t\twhile div // 2 != 0:\n\t\t\tn = n ^ div // 2\n\t\t\tdiv = div // 2\n\t\treturn n\n", "class Solution:\n\n\tdef grayToBinary(self, n):\n\t\tx = n\n\t\twhile True:\n\t\t\tif n == x ^ x >> 1:\n\t\t\t\treturn x\n\t\t\t\tbreak\n\t\t\tx = x ^ x >> 1\n"]

starter_code:
#User function Template for python3

class Solution:

    ##Complete this function

    # function to convert a given Gray equivalent n to Binary equivalent.

    def grayToBinary(self,n):

        ##Your code here

difficulty: EASY

source: geekforgeeks

skill_types: ['Bit manipulation', 'Data structures']

raw_problem:
Given N in Gray Code, find its binary equivalent. Return the decimal representation of the binary equivalent.

Example 1:

Input: N = 4
Output: 7
Explanation:
Given 4 representing gray code 110.
Binary equivalent of gray code 110 is 100.
Return 7 representing gray code 100.

Example 2:

Input: N = 15
Output: 10
Explanation:
Given 15 representing gray code 1000.
Binary equivalent of gray code 1000 is 1111.
Return 10 representing gray code 1111
ie binary 1010.

Example 3:

Input: N = 0
Output: 0
Explanation:
Zero remains the same in all systems.

Your Task:

You don't need to read input or print anything. Your task is to complete the function grayToBinary() which accepts an integer n as an input parameter and returns decimal of the binary equivalent of the given gray code.

Expected Time Complexity: O(log N)

Expected Auxiliary Space: O(1)

Constraints:

0 <= N <= 108

question:
Given N in Gray Code, find its binary equivalent. Return the decimal representation of the binary equivalent.
![image](1.png)
Example 1:

Input: N = 4
Output: 7
Explanation:
Given 4 representing gray code 110.
Binary equivalent of gray code 110 is 100.
Return 7 representing gray code 100.

Example 2:

Input: N = 15
Output: 10
Explanation:
Given 15 representing gray code 1000.
Binary equivalent of gray code 1000 is 1111.
Return 10 representing gray code 1111
ie binary 1010.
Example 3:

Input: N = 0
Output: 0
Explanation:
Zero remains the same in all systems.

Your Task:
You don't need to read input or print anything. Your task is to complete the function grayToBinary() which accepts an integer n as an input parameter and returns decimal of the binary equivalent of the given gray code.

Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)

Constraints:
0 <= N <= 10^{8}

data_split: test