Posts

191.Number Of 1 Bits

 Problem link => https://leetcode.com/problems/number-of-1-bits/ Code link => https://github.com/booleanbug/75-LeetCode/new/main Logic =>     First understand the unsigned format like uint8_t,uint16_t,uint32_t,uint64_t. Then right shift the number and take & with one,so that you can see whether that bit is 1 or 0 then add it to final answer.   SIMPLE QUESTION.

CODECHEF CONTEST WRITEUP (RANGEASSIGN DIV 4)

 Logic =>      We can have atmost 2 distinct numbers if we have 1 distinct number then whole array is same or arr[0] == arr[n-1] [1,1,1,1] = [1,1,1,1] = [1] [1,2,3,1] = [1,1,1,1] = [1] If we have 2 distinct number then whole array then array will be divided into two parts =>  [1,2,3,1,5,6,8,5] = [1,1,1,1,5,5,5,5] = [1,5]     Conditions => if a[0] == a[n-1] then yes else  for(int i = 1 ; i < n ; i++){ if(arr[0] == arr[i] & arr[i+1] == arr[n-1] then YES then NO CODE =  # include < stdio.h > # include < stdlib.h > int main ( void ) {         int t ;     scanf (" %d ", & t );         while ( t -- ){                 int n ;         scanf (" %d ", & n );                 int arr [ n ];         for ( int i = 0 ; i < n ; i ++ ){             scanf (" %d ", & arr [ i ]);         }                 int flag = 0 ;         if ( arr [ 0 ] == arr [ n - 1 ]){             flag = 1 ;         } else {             fo

FINDING GCD OF ARRAY IN O(logn)

  Prologue     Actually i was solving the codechef contest questions,then i came to a logic that required to calculate the gcd of array in order to solve that question,but i applied algorithm for gcd which had O(n2) time complexity and the result was TIME LIMIT EXCEEDED .Then I came across following algo which has O(nlogn)  which solved the problem.     Basic logic was as follows => gcd(a,b,c) = gcd(a,gcd(b,c)) | gcd(gcd(a,b),c) | gcd(b,gcd(a,c)) gcd(a,b,c,d) = gcd(a,gcd(b,c,d)) | gcd(b,gcd(a,c,d)) & so on .... and so on .....     So we will apply following core code => finalGcd = arr[0] for i in [1,n-1]: finalGcd = gcd(finalGcd,arr[i]] CODE  # include < stdio.h > # include < stdlib.h > int gcd ( int a , int b ){     if ( a == 0 ){         return b ;     }     return gcd ( b % a , a ); } int findGcd ( int * arr , int n ){     int result = arr [ 0 ];     for ( int i = 1 ; i < n ; i ++ ){         result = gcd ( arr [ i ], result );         i

3 MAPPING TECHNIQUES

Image
 WHAT IS MAPPING?      We need to bring data from the main memory to the cache for reducing the access time for the CPU as the cache is closer to the CPU than the main memory.  ASSOCIATIVE MAPPING     Data from main memory are placed randomly in cache.Let us say we have 16 bit memory address then out of that we have 12 bit tag bits & 4 bit word bits .That is cache will have total 2^12 blocks and each block will have 2^4 data words.if get 1111111111111111 then tag bits is 111111111111 & word bits is 1111,that is we will look for block with tage of 111111111111 and in that block we will search for 16th word block.refer the figure =>  benefits of associative mapping are like  No thrashing as it happens in direct mapping  DIRECT MAPPING     Same like above , if we use 16 bit addressing then tag bits have 5 bits,block bits of 7bits & word bits have 4 bits .Word bit identifies the column number,block bit identifies the row number & tag bits refers the corresponding address

How functions work in low level ?

Image
  BY USING PROCESSOR REGISTERS     Arguments that we pass to functions and results given by functions are nothing but parameters and the exchange of these data is called parameter passing. Parameter passing can be done by processor registers, processor stack, or by using memory stack.     What we will do is we will use registers 2,3,4,5 for parameter passing and data manipulation, but this is good when we require fewer parameters but when the number of parameters increases we cant use processor registers as these registers are limited.   BY USING PROCESSOR STACK     The address of the start of the array and the number of elements in the array are pushed in the stack and adding function is called when adding a function called this function computes the sum and places the result on the stack.          As the subroutine uses 4 registers it needs to save the content of these 4 registers somewhere so it pushes the content of all 4 registers on the stack computes the sum and stores the sum i

VIRTUAL MEMORY

Image
  Basic Idea Of Virtual Memory     Let us say we have a game of 50GB and RAM of 8 GB then by logic we will think that 50GB is greater than 8GB so the game can't fit in RAM so the game cant work. This is not the computers and world work pal...     Of 50GB let us say we require only 2 GB of data of RAM for making a game run and RAM is   8GB, yes we will put those data in RAM that is in use and others in physical memory (disk ) that are not in use right now.     The above process is done by the concept of virtual memory, it will show that it is doing hard work (running  50GB in 8GB space) but actually, it is doing smart work (running 2GB in 8GB).     Take a look at the following diagram =>       1. Processor issues for a virtual address asking for a physical address 2. Memory Management Unit converts the virtual address into a physical address using some internal methods. 3. You get data from that physical address either from cache or from main memory if that is not found in both o