abhinav700's blog

By abhinav700, history, 20 months ago, In English

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]; } };
  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
20 months ago, # |
  Vote: I like it +5 Vote: I do not like it

There are a couple of issues. The third argument to memset is supposed to be the number of bytes in the whole range you are setting (in this case sizeof(dp)), but you are passing in the size of a single element. However, the bigger issue is that memset is designed to set every byte to the same value, whereas it seems that you really want to set each 8-byte element of the array to 2.0. This means memset won't work; try using std::fill or std::fill_n instead.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    bigger issue is that memset is designed to set every byte to the same value, whereas it seems that you really want to set each 8-byte element of the array to 2.0 can you explain this statement please?

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We can use memset() to set all values as 0 or -1 for integral data types also. It will not work if we use it to set as other values. The reason is simple, memset works byte by byte.

      https://www.geeksforgeeks.org/memset-in-cpp/

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Each double takes up 8 bytes of space. The double 2.0 is represented by 01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 in binary, so to fill an array of doubles with 2.0, you really want to fill a range of memory with the repeating pattern 01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ....*

      However, memset sets each byte in the range to the same value. While you could use memset to fill a range of memory with patterns like 01101010 01101010 01101010 ... where each byte is the same, you could not create patterns like 01101010 11110000 01101010 11110000 where some bytes are different. The pattern you want to create has some bytes with different values, so you cannot use memset.

      *Technically, this assumes a big-endian layout, but that doesn't matter for this question.

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The pattern you want to create has some bytes with different values

        So this is my understanding of the problem.

        yes we can use memset,as long as the value assigned using it is under 1 byte. But since 2.0 needs more than one bytes, it will need a pattern like 01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 which is not possible because the memset assigns same value to all bytes.

        so either it can assign 01000000 or 00000000 but not the double values

        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This is roughly correct. The issue isn't being over 1 byte though (every double takes 8 bytes); it's that not all of the 8 bytes are the same. You can assign some doubles using memset, but only the ones where every byte is the same (such as 0, represented as 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000). This also applies to other data types: you can use memset to fill an array of ints with a value where every byte is the same (such as 0, represented as 00000000 00000000 00000000 00000000, or -1, represented as 11111111 11111111 11111111 11111111), but not other values like 1.