Recently, I was going through segment tree problems list and encountered this problem

It introduced me to the Euler's Totient Formula and it took multiple attempts for me to understand the concept, because of the mathematical notations and terms used. So I thought of creating of this resource for me to understand the formula in a more intutive way, and hope it will help other beginners also.

I have started from the core prime number concepts and have built up to the final formula.

I hope this is helpful.

Prime Numbers

Integers > 1 with exactly two divisors.
Used in: divisibility, coprimality, modular arithmetic.

Coprime numbers

Two numbers are coprime if:
They do not share any prime factor.

Examples:

gcd(8, 15) = 1 8 = 2³ 15 = 3 × 5 → No common prime → coprime

• gcd(12, 18) = 6 12 = 2² × 3 18 = 2 × 3² → Both share prime 2 and 3 → not coprime

So “coprime” simply means: No prime number divides both.

• Two numbers are are coprime if: gcd(a, b) = 1

• All numbers are coprime with 1 by definition

Prime Factorization

Every integer can be uniquely written as product of prime numbers.
Examples:

• 12 = 2 × 2 × 3 = 2² × 3¹

• 18 = 2 × 3 × 3 = 2¹ × 3²

• 20 = 2 × 2 × 5 = 2² × 5¹

• 15 = 3 × 5 = 3¹ × 5¹

• 7 = 7¹ (just prime)

Why is this important?
Because prime numbers act like the building blocks of integers.

Euler's Totient function φ(n)

φ(n) counts how many numbers from 1 to n are coprime to n. In other words:
count numbers ≤ n that share NO prime with n

Example: n = 12
prime factors = {2, 3}

numbers 1 to 12:
  1 2 3 4 5 6 7 8 9 10 11 12

remove numbers sharing prime 2:
  2,4,6,8,10,12

remove numbers sharing prime 3:
  3,6,9,12

remaining:
  1, 5, 7, 11

so φ(12) = 4.

Key Idea

A number is bad if it is divisible by any prime dividing n.

Take n = 12 = 2² × 3¹

Primes: 2, 3

• If x divisible by 2 → x not coprime

• If x divisible by 3 → x not coprime

This is the only reason. Nothing else makes a number non-coprime.

So everything reduces to:
Check divisibility by prime factors of n.

This is why prime factorization and φ(n) are directly connected.

Derivation for euler's formula

We can observe that, for the range 1 to n, there will be n/x multiples of x.

so suppose there are two prime factors x, y

Then, Euler(n) = n(1 - 1/x)(1 - 1/y)

How?

(n — n/x) => numbers which are not multiple of x. Let these leftover numbers be called n2

from these n2, we want to remove the multiples of y

so, n2 * ( 1 - 1 / y) are left over numbers. Let this be called n3.

n3 reperesents all the number which does not have prime numbers x and y as factors

suppose there was one more factor z

then we would do n4 = n3 * (1 - 1 / z)

Thus we arrive at the final answer when we expand this equation

Euler(n) = n3 * (1 - 1/z)

= n2 * (1 - 1/ y) * (1 - 1/z)

= (n - n / x) * (1 - 1 / y) * (1 - 1 / z)

= n * (1 - 1 / x) * (1 - 1 / y) * (1 - 1 / z)

Like this, if we want to find Euler(n) where n = x1^a1 * x2^a2 * x3^a3 .... * xn^bn

where, x1, x2, xn are prime numbers and a1, a2, a3 are the powers to which they are raised,

We can say that:

Euler(n) = n *(1 - 1 / x1) * (1 - 1 / x2) * ... (1 - 1 / xn)

In some solutions, we cut down the flag as demonstrated in this blog post

I referred to the AI for help and it says that a DP state can be reused only if it is path independent.

I am new to the digit DP am not able to understand the core reasoning behind this statement

Can someone explain it please?

Are there any good resources which describe the solution to following pattern problems:

Suppose You are given a tree of N nodes. You are given two arrays of size N: cost, value, where value[i] represents the money that you get from selling Node i, and Cost[i] represents the budget spent to buy i. You are also given a budget Variable B. Total money spent to buy nodes cannot be more than B. Find the maximum profit you can get.

Recently encountered this problem. Tried going through the solution, but none of them give the proper explanation for this. Just some description of the code.

The leetcode problem based on this pattern: Link

While declaring a link list, why do we create a new Node using Node* node = new Node(value) ? Can't we simply use Node node(val) if not, then why? and if we can, what are changes to our code we will have to make while using later syntax, for basic operations on link lists?

I was revising link list, and although I can solve the questions, I was confused with this syntax.

I was doing a question on leetcode and the part of it's solution required to find the rightmost set bit of an integer(it can also be negative).It is given that integer is a 32 bit number in constraints.

While finding out the position of right most bit using below function

int findPos(int allXor){
        int flag=1;
        int i;
        for( i=0;i<=32;i++)
            if((1<<i) & allXor )
                break;
        return i;
    }

i am unable to understand that how 1<<32 is going to work. It is because we are given a 32 bit number and 1<<32 would represent the integer which has it's 33rd bit set right? when i use i<=31 in this question i get the wrong answer.

Can someone pls explain what is happening here?

QUESTION LINK: https://leetcode.com/problems/single-number-iii/

FULL CODE:

class Solution {
public:
    int findPos(int allXor){
        int flag=1;
        int i;
        for( i=0;i<=32;i++)
            if((1<<i) & allXor )
                break;
        return i;
    }
    
    vector<int> singleNumber(vector<int>& nums) {
        if(nums.size()==2)
            return nums;
        vector<int> ans;
        int allXor=0;
        for(auto it: nums)
            allXor^=it;
        int bitPos=findPos(allXor);
        // cout<<allXor<<" "<<bitPos<<endl;
        vector<int> part1,part2;
        
        for(auto it: nums){
            if((1<<bitPos)&it)
                part1.push_back(it);
            else
                part2.push_back(it);
        }
        
        int element1=0,element2=0;
        for(auto it : part1)
        {
              element1^=it;
              cout<<it<<" ";
        }
        cout<<endl;
        for(auto it : part2)
        {
               element2^=it;
                cout<<it<<" ";
        }
        return {element1,element2};
    }
};

Earlier, i was solving a problem. When i went to discuss section to see the solutions, there was a person who was following a syntax of for loop which i was not able to understand.

it was as follows: for (char &c : word) where word is of type std::string. can someone explain me how is it different from for (char c : word)? because i was getting run time error when i tried to remove & from c.

i tried running it my console, but still was not able to understand it's working properly.

i am doing a leetCode question which requires a 3d array for memorisation. i have followed every rule of using the memset function and creating the arrays still the array is not getting initialised with the value specified in memset function. I have been stuck on this from yesterday. Can someone pls help? Problem Link: https://leetcode.com/problems/knight-probability-in-chessboard/

CODE:

class Solution {
public:
        int dir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{2,-1},{2,1},{1,2},{1,-2}};

        double solve(int n,int k,int r,int c,double dp[101][26][26]){
        if(r<0 || r>=n || c<0 || c>=n)
            return 0;
        if(k==0)
            return 1.0;
        if(dp[k][r][c]!=2.0){
            cout<<"k r,c : "<<k<<" "<<r<<" "<<c<<endl;
            cout<<"value : "<<dp[k][r][c]<<endl<<endl;
            return dp[k][r][c];            
        }
        double rate=0;
        for(int i=0;i<8;i++){
             rate+=(solve(n,k-1,r+dir[i][0],c+dir[i][1],dp)*0.125);
        }
        return dp[k][r][c]= rate;
    }
    double knightProbability(int n, int k, int row, int column) {
        double dp[101][26][26];
        memset(dp,2.0,sizeof(dp[0][0][0]));
        cout<<dp[0][0][0];
        solve(n,k,row,column,dp);
        return dp[k][row][column];
    }

};

#include "bits/stdc++.h"
using namespace std;
 
int main()
{
 long long int q;
 cin>>q;
 while(q--)
 {
     long long int n,k;
     cin>>n>>k;
     vector<long long int> pos(k);
     for(long long int i=1;i<=k;i++)
     {
         cin>>pos[i];
     }
     vector<long long int> temp(k);
     for(long long int i=1;i<=k;i++)
     cin>>temp[i];

    vector<long long int> output(n,1e8);
    
   for(long long int i=1;i<=n;i++)
   {
       for(long long int j=1;j<=k;j++)
       {
           output[i]=min(output[i],temp[j]+abs(pos[j]-i));
       }
   }

    for(long long int i=1;i<=n;i++)
    cout<<output[i]<<" ";

    cout<<endl;
     
 }   
 return 0;
}