Horje
Find all the factors of given Number and their bitwise XOR

Given an integer N, the task is to find all the factors (excluding itself) of the number N and their XOR.

Examples:

Input: N = 8 
Output:
Divisors are: 1 2 4 
Xor: 7
Explanation:  1, 2 and 4 are all factors of 8 and 1^2^4 = 7.

Input: N = 25
Output:
Divisors are: 1 5 
Xor: 4

Approach: Follow the below idea to solve the problem:

Store all the factors of the given number N and calculate the xor of all the factors

Follow the steps to solve this problem:

  • Initialize a variable Xor = 0
  • Create vector factors1 and factors2 for storing factors from 1 to sqrt(N) and from sqrt(N) to N.
  • Traverse the array from 1 till sqrt(N)
    • If N % i = 0, append i in factors1 and Xor = Xor^i
    • And check If N / i != i, append N / i in factors2 and Xor = Xor^(n / i)
  • After executing the loop, insert elements of factors2 in factors1 in reverse order
  • Pop the element N from the factors1 vector.
  • Print the factors1 vector and return Xor^N as we have already calculated N in the Xor.

Below is the implementation of the above approach.

C++

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all the divisors
// of N (excluding N) in sorted order
// and returning Xor of all factors of
// N except itself
int findAllFactors(int n)
{
    int Xor = 0;
 
    // To store factors from 1 to sqrt(n)
    vector<int> factors1;
 
    // To store factors from sqrt(n) to n
    vector<int> factors2;
 
    // Traverse from 1 to sqrt(n)
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            factors1.push_back(i);
            Xor ^= i;
 
            if (n / i != i) {
                factors2.push_back(n / i);
                Xor ^= (n / i);
            }
        }
    }
 
    // Append factors2 in factors1 in reverse order
    factors1.insert(factors1.end(), factors2.rbegin(),
                    factors2.rend());
 
    // Pop back 1 element from resultant
    // vector to remove N from factors
    factors1.pop_back();
 
    cout << "Divisors are: ";
 
    for (auto i : factors1) {
        cout << i << " ";
    }
    cout << endl;
 
    cout << "Xor: ";
 
    return Xor ^ n;
}
 
// Driver Code
int main()
{
    int N = 8;
 
    // Function call
    cout << findAllFactors(N) << endl;
    return 0;
}

Java

import java.io.*;
import java.util.*;
 
public class GFG {
  static void findAllFactors(int N)
  {
    long Xor = 0;
    ArrayList<Integer> factor1
      = new ArrayList<Integer>();
    ArrayList<Integer> factor2
      = new ArrayList<Integer>();
    for (int i = 1; i * i <= N; i++) {
      if (N % i == 0) {
        factor1.add(i);
        Xor = Xor ^ i;
        if (N / i != i) {
          int M = N / i;
          factor2.add(M);
          Xor = Xor ^ (N / i);
        }
      }
    }
    for (int i = factor2.size() - 1; i >= 1; i--) {
      factor1.add(factor2.get(i));
    }
    System.out.println("Divisors are : " + factor1);
    Xor = Xor ^ N;
    System.out.println("Xor : " + Xor);
  }
  public static void main(String[] args)
  {
    int N = 8;
    findAllFactors(N);
  }
}
 
// This code is contributed by garg28harsh.

Python3

# python code for the above approach
import math
 
# Function to find all the divisors
# of N (excluding N) in sorted order
# and returning Xor of all factors of
# N except itself
def findAllFactors(n):
    Xor = 0
 
    # To store factors from 1 to sqrt(n)
    factors1 = []
 
    # To store factors from sqrt(n) to n
    factors2 = []
 
    # Traverse from 1 to sqrt(n)
    for i in range(1, int(math.sqrt(n)) + 1):
        if (n % i == 0):
            factors1.append(i)
            Xor ^= i
 
            if (n // i != i):
                factors2.append(n // i)
                Xor ^= (n // i)
 
    # Append factors2 in factors1 in reverse order
    factors1 = factors1 + factors2[::-1]
 
    # Pop back 1 element from resultant
    # vector to remove N from factors
    factors1.pop()
 
    print("Divisors are: ", end="")
 
    for i in factors1:
        print(i, end=" ")
 
    print()
 
    print("Xor: ", end="")
 
    return Xor ^ n
 
# Driver Code
if __name__ == "__main__":
 
    N = 8
 
    # Function call
    print(findAllFactors(N))
 
    # This code is contributed by rakeshsahni

C#

using System;
using System.Collections.Generic;
public class GFG
{
    static void findAllFactors(int N)
    {
        long Xor = 0;
        List<int> factor1 = new List<int>();
        List<int> factor2
          = new List<int>();
        for (int i = 1; i * i <= N; i++)
        {
            if (N % i == 0)
            {
                factor1.Add(i);
                Xor = Xor ^ i;
                if (N / i != i)
                {
                    int M = N / i;
                    factor2.Add(M);
                    Xor = Xor ^ (N / i);
                }
            }
        }
        for (int i = factor2.Count - 1; i >= 1; i--)
        {
            factor1.Add(factor2[i]);
        }
        Console.Write("Divisors are : ");
 
        foreach(int item in factor1){
            Console.Write(item + " ");
        }
 
        Console.WriteLine();
        Xor = Xor ^ N;
        Console.WriteLine("Xor : " + Xor);
    }
    public static void Main()
    {
        int N = 8;
        findAllFactors(N);
    }
}
 
// This code is contributed by Saurabh Jaiswal

Javascript

// Javascript code for the above approach
 
    // Function to find all the divisors
    // of N (excluding N) in sorted order
    // and returning Xor of all factors of
    // N except itself
    function findAllFactors(n)
{
    let Xor = 0;
 
    // To store factors from 1 to sqrt(n)
    let factors1 = [];
 
    // To store factors from sqrt(n) to n
    let factors2 = [];
 
    // Traverse from 1 to sqrt(n)
    for (let i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            factors1.push(i);
            Xor ^= i;
 
            if (n / i != i) {
                factors2.push(n / i);
                Xor ^= (n / i);
            }
        }
    }
 
    // Append factors2 in factors1 in reverse order
    for (let i = factors2.length - 1; i >= 0; i--) {
        factors1.push(factors2[i]);
    }
 
    // Pop back 1 element from resultant
    // vector to remove N from factors
    factors1.pop();
    document.write("Divisors are: " + factors1);
 
    return Xor ^ n;
}
 
// Driver Code
let N = 8;
 
// Function call
console.log("Xor : " + findAllFactors(N));
 
// This code is contributed by garg28harsh.

Output

Divisors are: 1 2 4 
Xor: 7

Time Complexity: O(N1/2), where N is the given integer.
Auxiliary Space: O(N1/2), for storing all the factors of the given integer.


 


Reffered: https://www.geeksforgeeks.org

Greedy

Related
Minimize the size of Array by doing maximum absorptions Minimize the size of Array by doing maximum absorptions
Minimize insertions in Array to make ratio of each pair as K Minimize insertions in Array to make ratio of each pair as K
Maximise length of smallest group by dividing Binary String into K groups of same bit Maximise length of smallest group by dividing Binary String into K groups of same bit
Minimize operations to reduce A or B to 0 by reducing A from B or B from A Minimize operations to reduce A or B to 0 by reducing A from B or B from A
Maximum power in N levels from K such that defeating boss at level A[i] increases power by B[i] Maximum power in N levels from K such that defeating boss at level A[i] increases power by B[i]

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje