Hamming equivalent
Source: codechef
Difficulty: 1298

Hamming equivalent
You are given a permutation$P$of length$N$. You are allowed to perform the following operation any number of times:
Choose any two numbers$P_i$and$P_j$such that the number of set bits ($1$s in their binary representation) is the same, and swap them.
Determine if it is possible to sort the permutation in ascending order using this operation. If possible, print Yes; otherwise, print No.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains a single integer$N$, denoting the length of the permutation$P$.
The second line contains$N$space-separated integers$P_1, P_2, P_3, \ldots, P_N$, denoting the permutation$P$.
Output Format
For each test case, output on a new line the answer —
YES
it is possible to sort$P$in ascending order using this operation, and
NO
otherwise.
Each character of the output may be printed in either uppercase or lowercase. For example, the strings
YES
,
yeS
,
yes
, and
YeS
will all be treated as identical.
Constraints$1 \leq T \leq 10^5$$1 \leq N \leq 2\cdot 10^5$$P$is a permutation of$\{1, 2, 3, \dots N\}$The sum of$N$over all test cases does not exceed$5 \cdot 10^5$.
Sample 1:
Explanation:
Test case$2$:
: We can swap$P_1$and$P_2$because both have exactly one$1$in their binary representations.$[\underline{2, 1}] \xrightarrow{i = 1,  j = 2} [1, 2]$.
Test case$3$:
: There is no possible way to sort$P$.
Test case$4$:
:
We can swap$P_2$and$P_4$because both have exactly one$1$in their binary representations$[4, \underline{1}, 3, \underline{2}] \xrightarrow{i = 2,  j = 4} [4, 2, 3, 1]$.
We can swap$P_1$and$P_4$because both have exactly one$1$in their binary representations$[\underline{4}, 2, 3, \underline{1}] \xrightarrow{i = 1,  j = 4} [1, 2, 3, 4]$.

Sample Input:
4
1
1
2
2 1
3
3 1 2
4
4 1 3 2

Sample Output:
Yes
Yes
No
Yes

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<int> arr;
        for(int i=0;i<n;i++)
        {
            int x ;
            cin>>x;
            arr.push_back(x);
        }
        bool isPossible = true;
        for(int i=0;i<n;i++)
        {
            if(__builtin_popcount(i+1) != __builtin_popcount(arr[i]))
                {
                    isPossible = false;
                    break;
                }
        }
        if(isPossible)
            cout<<"Yes\n";
       else
            cout<<"No\n";
        
    }
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func countOnes(numbers []int) []int {
    result := make([]int, len(numbers))
    for i, num := range numbers {
        count := 0
        for num > 0 {
            count += num & 1
            num >>= 1
        }
        result[i] = count
    }
    return result
}

func isValidSequence(size int, sequence []int) string {
    bitCounts := countOnes(sequence)
    for index := 0; index < size; index++ {
        expectedCount := 0
        num := index + 1
        for num > 0 {
            expectedCount += num & 1
            num >>= 1
        }
        if bitCounts[index] != expectedCount {
            return "No"
        }
    }
    return "Yes"
}

func main() {
    reader := bufio.NewReader(os.Stdin)
    var t int
    fmt.Fscanf(reader, "%d\n", &t)

    for caseNum := 0; caseNum < t; caseNum++ {
        var n int
        fmt.Fscanf(reader, "%d\n", &n)

        line, _ := reader.ReadString('\n')
        line = strings.TrimSpace(line)
        numStrings := strings.Split(line, " ")
        sequence := make([]int, n)
        for i, numStr := range numStrings {
            sequence[i], _ = strconv.Atoi(numStr)
        }

        result := isValidSequence(n, sequence)
        fmt.Println(result)
    }
}

Java solution:
/**
 * @author Abhisek Singh (Zyroßeast)
 * 
 */

import java.io.DataInputStream;
import java.io.IOException;

public class Main {

   /**
    * Main logic for the program.
    * 
    * @param args Not Used anywhere
    * @throws IllegalArgumentException If any Error happens while processing data.
    * 
    */
    public static void main(String[] args) throws IllegalArgumentException {
        initializeIO();
        try {
            int __ = nextInt(), i, n;
  
            while(__ -- > 0) {
                n = nextInt();

                for(i = 1; i <= n; i++) {
                    if (countBits(i) != countBits(nextInt())) break;
                }
                
                if (i < n) skipLine();
                
                outData.append(i == n + 1 ? "Yes\n" : "No\n");
            }
        
        } catch(IllegalArgumentException iae) {
            close();
            throw iae;
        }
        
        close();
    }
    
    
    public static int countBits(int n) {
        var count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        
        return count;
    }
    
    
    
    
    
    
    
   /* The methods below are used for low level IO operations
    that will be used in the program. */
     
   /** InputStream with implemented buffering for faster input */
    private static DataInputStream dis;
   /** Buffer for input */
    private static byte[] buffer;
   /** Variables for reading buffer */
    private static int bytesRead, bufferPos;
   /** Unsynchronized Mutable String to store Output */
    private static StringBuilder outData;
    
   /**
    * Initializes the IO objects.
    * To be called before using IO methods.
    * 
    */
    private static void initializeIO() {
        dis = new DataInputStream(System.in);
        buffer = new byte[1 << 16];
        read();
        
        outData = new StringBuilder();
    }
    
   /**
    * Closes IO objects after execution.
    * 
    */
    private static void close() {
        try {
            System.out.print(outData);
            dis.close();
        }
        catch(IOException e) {
        }
    }
    
   /** To store next byte in buffer for Operations. */
    private static byte c;
   /** To store if a integer type data is negative or not. */
    private static boolean neg;
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Integer data from the input data
    * 
    */
    private static int nextInt() throws IllegalArgumentException {
        skipWhiteSpace();
        int temp = 0;
        
        neg = (c == '-');
        if(neg) {
            read();
        }

        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10 + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        
        return neg ? -temp : temp;
    }
    
   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * @return The Integer array with the specified number of elements.
    * 
    */
    private static int[] nextIntArr(int n) throws IllegalArgumentException {
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++) arr[i] = nextInt();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not an integer type.
    * 
    * @return The next Long data in the input data
    * 
    */
    private static long nextLong() throws IllegalArgumentException {
        skipWhiteSpace();
        long temp = 0;

        neg = (c == '-');
        if (neg) {
            read();
        }
        
        do {
            if(!isDigit()) {
                throw new IllegalArgumentException();
            }
            
            temp = temp * 10L + c - '0';
            read();
        } while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1));

        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an long type.
    * @return The Long array with the specified number of elements.
    * 
    */
    private static long[] nextLongArr(int n) throws IllegalArgumentException {
        long[] arr = new long[n];
        for(int i = 0; i < n; i ++) arr[i] = nextLong();
        return arr;
    }
    
   /**
    * @throws IllegalArgumentException If the next input data is not float or integer.
    * 
    * @return The next Double data in the input stream.
    * 
    */
    private static double nextDouble() {
        skipWhiteSpace();
        double temp = 0.0d;
        
        neg = (c == '-');
        if(neg) {
            read();
        }
        
        if(c != '.') {
            do {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                read();
            } while(c != '.' && !(c == '\n' || c == ' ' || c == '\r') && (c != -1));
        }
        
        if(c == '.') {
            double div = 1.0d;
            read();
            
            while(!(c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
                if(!isDigit()) {
                    throw new IllegalArgumentException();
                }
            
                temp = temp * 10.0d + c - '0';
                div *= 10.0d;
                read();
            }
            
            temp /= div;
        }
        
        return neg ? -temp : temp;
    }

   /**
    * @param n The size of the array.
    * @throws IllegalArgumentException If the next input data is not an double type.
    * @return The Double array with the specified number of elements.
    * 
    */
    private static double[] nextDoubleArr(int n) throws IllegalArgumentException {
        double[] arr = new double[n];
        for(int i = 0; i < n; i ++) arr[i] = nextDouble();
        return arr;
    }
    
   /**
    * Checks if a byte is number or not.
    * 
    */
    private static boolean isDigit() {
        return (c >= '0' && c <= '9');
    }
  
   /** Stores the initial length of the given StringBuilder in the following functions. */
    private static int length;
   
   /**
    * Writes the remaining data from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder getLine(StringBuilder sb) throws IllegalArgumentException {
        sb.setLength(0);
        
        while(c != -1) {
            if(c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == 0) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next line from the current line from the input data in the given StringBuilder.
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder nextLine(StringBuilder sb) {
        skipLine(); getLine(sb);
        return sb;
    }
    
   /**
    * Appends the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @throws IllegalArgumentException If there is no byte left in input data.
    * @return The StringBuilder object after filling it.
    *
    */
    private static StringBuilder addNext(StringBuilder sb) throws IllegalArgumentException {
        skipWhiteSpace();
        length = sb.length();
        
        while(c != -1) {
            if(c == ' ' || c == '\n' || c == '\r') {
                break;
            }
            
            sb.append((char)c);
            read();
        }
        
        if(sb.length() == length) {
            throw new IllegalArgumentException();
        }
        
        return sb;
    }
    
   /**
    * Writes the next word from the input data in the given StringBuilder
    * 
    * @param sb StringBuilder object in which the data will be stored.
    * @return The StringBuilder object after refilling it.
    *
    */
    private static StringBuilder next(StringBuilder sb) {
        sb.setLength(0);
        addNext(sb);
        return sb;
    }
    
   /**
    * Skips any prevailing space or empty lines.
    * 
    */ 
    private static void skipWhiteSpace() {
        while((c == '\n' || c == ' ' || c == '\r') && (c != -1)) {
            read();
        }
    }
   
   /**
    * Skips any prevailing space.
    * 
    */
    private static void skipSpace() {
        while(c == ' ' && c != -1) {
            read();
        }
    }
     
   /**
    * Skips a line from the input stream.
    * 
    */
    private static void skipLine() {
        while(c != '\n' && c != '\r' && c != -1) {
            read();
        }
        
        while(c != -1 && (c == '\n' || c == '\r')) {
            read();
        }
    }
    
   /**
    * Skips a word from the input stream.
    * 
    */
    private static void skipWord() {
        while(c != '\n' && c != ' ' && c != '\r' && c != -1) {
            read();
        }
        
        read();
    }
    
   /**
    * Refills the buffer with new data.
    * 
    */
    private static void fillBuffer() throws IOException {
        bytesRead = dis.read(buffer, bufferPos = 0, buffer.length);
        
        if(bytesRead == -1) {
            buffer[0] = -1;
        }
    }
   
   /**
    * Reads the next byte from the input data and stores it in {@link c}
    * 
    */
    private static void read() {
        if(bufferPos >= bytesRead) {
            try {
                fillBuffer();
            }
            catch(IOException e) {
            }
        }
        
        c = buffer[bufferPos ++];
    }
}

JavaScript solution:
// your code goes here
let V8Flags = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];

if (V8Flags.length > 0) {
        process.execArgv.push('--v8-options=' + V8Flags.join(' '));
}

let inputBuffer = Buffer.allocUnsafe(1e7);
let inputIndex = 0,
        inputLength = 0;
let outputBuffer = Buffer.allocUnsafe(1e7);
let outputIndex = 0;

let fs = require('fs');
inputLength = fs.readSync(process.stdin.fd, inputBuffer, 0, inputBuffer.length, null);

let readInt = () => {
        let n = 0,
                s = 1;
        while (inputBuffer[inputIndex] < 48 || inputBuffer[inputIndex] > 57) {
                if (inputBuffer[inputIndex] === 45) s = -1;
                inputIndex++;
        }
        while (inputIndex < inputLength && inputBuffer[inputIndex] >= 48 && inputBuffer[inputIndex] <= 57) {
                n = n * 10 + (inputBuffer[inputIndex++] - 48);
        }
        return n * s;
}

let isFirstInLine = true;
let writeStr = (s, isLast = false) => {
        if (!isFirstInLine) outputBuffer[outputIndex++] = 32;
        for (let i = 0; i < s.length; i++) {
                outputBuffer[outputIndex++] = s.charCodeAt(i);
        }
        isFirstInLine = isLast;
        if (isLast) {
                outputBuffer[outputIndex++] = 10;
                isFirstInLine = true;
        }
}

// Template Ends here!

let x = (n) => {
        let c = 0;
        while (n > 0) {
                c += (n & 1);
                n >>= 1;
        }
        return c;
}

let y = (p) => {
        let g = {},
                o = [...p];
        for (let i = 0; i < p.length; i++) {
                let b = x(p[i]);
                if (!g[b]) g[b] = [];
                g[b].push(i);
        }
        
        for (let b in g) {
                let v = g[b].map(i => o[i]);
                v.sort((a, b) => a - b);
                for (let i = 0; i < g[b].length; i++) {
                        p[g[b][i]] = v[i];
                }
        }
        
        for (let i = 1; i < p.length; i++) {
                if (p[i] < p[i - 1]) return false;
        }
        return true;
}

let t = readInt();
while (t--) {
        let n = readInt();
        let p = new Uint32Array(n);
        for (let i = 0; i < n; i++) p[i] = readInt();
        writeStr(y(p) ? "YES" : "NO", true);
}

fs.writeSync(process.stdout.fd, outputBuffer.slice(0, outputIndex));

Python solution:
# cook your dish here
for _ in range(int(input())):
    input()
    a = list(map(int, input().split()))
    b = sorted(a)
    print("YES" if all(bin(x).count('1') == bin(y).count('1') for x, y in zip(a, b)) else "NO")

Ruby solution:
def solve
  input = $stdin.read.split
  ptr = 0
  t = input[ptr].to_i
  ptr += 1
  results = []
  t.times do
    n = input[ptr].to_i
    ptr += 1
    a = input[ptr, n].map(&:to_i)
    ptr += n
    b = a.sort
    possible = true
    (0...n).each do |i|
      unless a[i].to_s(2).count('1') == b[i].to_s(2).count('1')
        possible = false
        break
      end
    end
    results << (possible ? "Yes" : "No")
  end
  puts results.join("\n")
end

solve